Поискал в инете, не мог найти описание алгоритма такой распространённой комбинаторной задачи как перебор элементов массива. Единственное что есть это как вычислить количество вариантов перебора, либо уже готовый код без особых объяснений. Может кто-нибудь объяснить алгоритм решения задачи(есть массив из N элементов, нужно получить N! неповторяющихся массивов, состоящих из тех-же элементов), или дать ссылку где такая вещь грамотно и подробно расписана.

Здравствуйте, Vladimir E., Вы писали:

VE>Поискал в инете, не мог найти описание алгоритма такой распространённой комбинаторной задачи как перебор элементов массива. Единственное что есть это как вычислить количество вариантов перебора, либо уже готовый код без особых объяснений. Может кто-нибудь объяснить алгоритм решения задачи(есть массив из N элементов, нужно получить N! неповторяющихся массивов, состоящих из тех-же элементов), или дать ссылку где такая вещь грамотно и подробно расписана.

Ключевое слово для поиска Permutations

Здравствуйте, deniok, Вы писали:

D>Здравствуйте, Vladimir E., Вы писали:

VE>>Поискал в инете, не мог найти описание алгоритма такой распространённой комбинаторной задачи как перебор элементов массива. Единственное что есть это как вычислить количество вариантов перебора, либо уже готовый код без особых объяснений. Может кто-нибудь объяснить алгоритм решения задачи(есть массив из N элементов, нужно получить N! неповторяющихся массивов, состоящих из тех-же элементов), или дать ссылку где такая вещь грамотно и подробно расписана.

D>Ключевое слово для поиска Permutations

По-русски — перестановки.

Пара дополнений:

В C++ в STL есть алгоритм

template<class BidIt>
    bool next_permutation(BidIt first, BidIt last);

осуществляющий над контейнером "следующую" (в лексикографическом порядке) перестановку; то есть последовательные вызовы будут давать

A B C -> A C B -> B A C -> ...

На Хаскелле здесь

Автор:
Дата: 12.02.07

или здесь

Автор: R.K.
Дата: 18.03.07

.

Здравствуйте, deniok, Вы писали:

D>Здравствуйте, deniok, Вы писали:

D>>Ключевое слово для поиска Permutations

D>По-русски — перестановки.

D>Пара дополнений:

D>В C++ в STL есть алгоритм
D>

D>template<class BidIt>
D>    bool next_permutation(BidIt first, BidIt last);
D>

D>осуществляющий над контейнером "следующую" (в лексикографическом порядке) перестановку; то есть последовательные вызовы будут давать
D>

D>A B C -> A C B -> B A C -> ...
D>

D>На Хаскелле здесь

Автор:
Дата: 12.02.07

или здесь

Автор: R.K.
Дата: 18.03.07

.

Пишу я на паскале, а по ключевым словам я уже говорил что пробовал искать, там либо чистый готовый код, либо ссылки битые, либо какие-то основы комбинаторики, где только говорится как количество вариантов подсчитать, а не как сделать оптимальный алгоритм чтобы он перебирал все значения, причём без повторений.

Здравствуйте, Vladimir E., Вы писали:

VE>Пишу я на паскале, а по ключевым словам я уже говорил что пробовал искать, там либо чистый готовый код, либо ссылки битые, либо какие-то основы комбинаторики, где только говорится как количество вариантов подсчитать, а не как сделать оптимальный алгоритм чтобы он перебирал все значения, причём без повторений.

В каком смысле оптимальный? У тебя в любом случае ответ даёт "комбинаторный взрыв" по использованию памяти. Поэтому C++-ый вариант c next_permutation часто удобнее всего. Если действительно необходимо получить все перестановки одновременно — прогоняешь в цикле next_permutation до тех пор, пока он может выполнить следующую перестановку, и на каждом шаге копируешь очередную перестановку в результирующий контейнер контейнеров:

while ( next_permutation(start, end) )
{
   copy(start, end, resContIt) ;
}

(Понятно, что исходно контейнер [start,end) должен быть отсортирован.)


А сам next_permutation реализовать не очень сложно, см., например, здесь.

Здравствуйте, deniok, Вы писали:

D>Здравствуйте, Vladimir E., Вы писали:

VE>>Пишу я на паскале, а по ключевым словам я уже говорил что пробовал искать, там либо чистый готовый код, либо ссылки битые, либо какие-то основы комбинаторики, где только говорится как количество вариантов подсчитать, а не как сделать оптимальный алгоритм чтобы он перебирал все значения, причём без повторений.

D>В каком смысле оптимальный? У тебя в любом случае ответ даёт "комбинаторный взрыв" по использованию памяти. Поэтому C++-ый вариант c next_permutation часто удобнее всего. Если действительно необходимо получить все перестановки одновременно — прогоняешь в цикле next_permutation до тех пор, пока он может выполнить следующую перестановку, и на каждом шаге копируешь очередную перестановку в результирующий контейнер контейнеров:

D>

D>while ( next_permutation(start, end) )
D>{
D>   copy(start, end, resContIt) ;
D>}
D>

D>(Понятно, что исходно контейнер [start,end) должен быть отсортирован.)

Немного офтопик, но тут первая перестановка не будет скопирована. Тут как раз редкий пример, когда do ... while идеально подходит.

Здравствуйте, _DAle_, Вы писали:

D>>

D>>while ( next_permutation(start, end) )
D>>{
D>>   copy(start, end, resContIt) ;
D>>}
D>>

D>>(Понятно, что исходно контейнер [start,end) должен быть отсортирован.)

_DA>Немного офтопик, но тут первая перестановка не будет скопирована. Тут как раз редкий пример, когда do ... while идеально подходит.

Да, спасибо, императивная квалификация напрочь утрачена
За каким же количеством вещей там нужно следить!

Здравствуйте, Vladimir E., Вы писали:

VE>Пишу я на паскале, а по ключевым словам я уже говорил что пробовал искать, там либо чистый готовый код, либо ссылки битые, либо какие-то основы комбинаторики, где только говорится как количество вариантов подсчитать, а не как сделать оптимальный алгоритм чтобы он перебирал все значения, причём без повторений.

Ну, первоисточник с подробным описанием — это Дональд Кнут. Какой номер тома — не помню.
Можно ещё поглядеть в Кормена или Седжвика...

А что касается описания алгоритма, так он довольно прост.

Пусть у нас есть набор (не обязательно уникальных элементов), и мы хотим получить все его перестановки.
Пусть мы умеем получать лексикографически (лг-) следующую перестановку из текущей. И пусть мы умеем получать лг-минимальную перестановку (эта процедура называется "сортировка" ). Тогда, начав с лг-минимума, мы последовательно переберём все.

Остался вопрос: как получать лг-следующую.
Пусть текущая перестановка выглядит так:
S = s[1],...,s[k-1],s[k],s[k+1],...,s[n],
где
— s[1]...s[k-1] в произвольном порядке,
— s[k]<s[k+1],
— s[k+1]>=s[k+2]>=...>=s[n]

Перестановки S' получаемые из S с сохранением порядка первых k элементов, т.е. s'[1]=s[1],...,s'[k]=s[k], не могут быть лг-больше, чем S, потому что s[k+1]..s[n] (невозрастающая последовательность) является лг-максимумом набора элементов хвоста.
Перестановки S", получаемые с перемещением любого из k-1 головных элементов, не являются лг-следующими, так как между S и S" есть по меньшей мере одна перестановка S' сохраняющая k-1 голову и перемещающая s[k].
Сейчас мы найдём её.

Пусть m — такой индекс, что k+1<=m<=n, s[k] < s[k+1]>=...>=s[m] > s[k] >= ... >= s[n]
Построим S' = s[1],...,s[k-1], s[m], s[n],...,s[m+1], s[k], s[m-1],...,s[k+1]
— голова совпадает с S;
— затем следует самый маленький из элементов, больших, чем s[k], — т.е. s[m]; это значит, что S' лг-больше S
— затем лг-минимум из набора хвостовых элементов без s[m], но с s[k]; поскольку хвост был обратно-упорядочен, то сортировка сводится к переворачиванию и вставке
Два последних пункта гарантируют, что S' лг-минимальна среди всех перестановок, лг-больших чем S. То есть, она является лг-следующей.

Вот и вся история.

Здравствуйте, Vladimir E., Вы писали:

VE>Поискал в инете, не мог найти описание алгоритма такой распространённой комбинаторной задачи как перебор элементов массива. Единственное что есть это как вычислить количество вариантов перебора, либо уже готовый код без особых объяснений. Может кто-нибудь объяснить алгоритм решения задачи(есть массив из N элементов, нужно получить N! неповторяющихся массивов, состоящих из тех-же элементов), или дать ссылку где такая вещь грамотно и подробно расписана.

здесь

Автор: sadomovalex
Дата: 13.07.04

пример с сочетаниями, который легко переделывается в перестановки. Код минимальный, разобраться несложно:

#include <vector>
#include <algorithm>
#include <numeric>
#include <iostream>

using namespace std;

void print(int i) { cout << i << " "; }
void printVector(const vector<int> &vct)
{
    for_each(vct.begin(), vct.end(), print); cout << endl;
}

void perm(int l, const int n, const vector<int>& src, vector<int>& dest)
{
    if (dest.size() == n)
    {
        printVector(dest);
        return;
    }
    
    for (int i = 0; i < n; i++)
    {
        if (find(dest.begin(), dest.end(), src[i]) == dest.end())
        {
            dest.push_back(src[i]);
            perm(i + 1, n, src, dest);
            dest.pop_back();
        }
    }
}

int main()
{
    vector<int> src, dest;
    src.push_back(1); src.push_back(2); src.push_back(3); src.push_back(4);
    
    perm(0, src.size(), src, dest);
    
    return 0;
}

Здравствуйте, Vladimir E., Вы писали:

VE>Может кто-нибудь объяснить алгоритм решения задачи(есть массив из N элементов, нужно получить N! неповторяющихся массивов, состоящих из тех-же элементов), или дать ссылку где такая вещь грамотно и подробно расписана.

здесь

Автор: ie
Дата: 23.02.07