Список всех перестановок заданного набора значений

Question

Меня интересуют сравнения различных методов/подходов, которые можно использовать для генерации всех потенциальных перестановок заданного набора.

Answer 1

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

Самый эффективный алгоритм, насколько мне известно, является Steinhaus algorithm. Он оптимален до мультипликативной константы в том смысле, что для генерации одной перестановки требуется только постоянное количество инструкций процессора (не считая инструкций, необходимых для ее распечатки, что не всегда необходимо).

Существует также очень простой алгоритм, который создает перестановки в лексикографическом порядке, которые вы, вероятно, сможете переосмыслить как рекурсивную процедуру самостоятельно, а производительность которой равна O (n.log (n) .log (n)), поэтому примерно то же самое, что генерировать список любым другим способом и сортировать его.

Edit: здесь псевдокод простого алгоритма:

void permute(Element[] permutationPrefix, Set rest) 
{ 
    if (rest.IsEmpty) { 
     // permutationPrefix is now a full permutation 
     print(permutationPrefix); 
    } else { 
     foreach (element in rest) { 
      permutationPrefix.Append(element); 
      permute(permutationPrefix, rest.Minus(element)) 
      permutationPrefix.Length--; // cut away the last item 
     } 
    } 
} 

Первоначально называют это с пустым permutationPrefix и rest держащего полный комплект; если этот набор является упорядоченной структурой данных, перестановки будут выводиться в лексикографическом порядке.

Обратите внимание, что мы копируем и модифицируем множество при каждом рекурсивном вызове, что является самой дорогостоящей операцией всего алгоритма, возможно, вместе с методом print. Стоимость одной заданной копии логарифмична в общем числе перестановок n; и поскольку глубина рекурсивного стека вызовов также логарифмична, следует оценка производительности O (n.log (n) .log (n)).

(Этот алгоритм также подходит для преобразования в хорошо вели себя генератор случайных перестановок.)

Answer 2

Этот вопрос уже задавался и ответил (много раз на самом деле):

Algorithm to generate all possible permutations of a list?

Permutations with a given integer

Лично я считаю, что алгоритм Стейнхауза чрезмерно задумывается о проблеме: это не намного быстрее, чем самая наивная реализация.

Java-подобный псевдокод наиболее наивной реализации:

List<List<Element>> generateAllPermutations(List<Element> input) 
{ 
    List<Element> output = new ArrayList<Element>(); 
    if (input.size() == 0) 
     return output; 
    for (Element first : input) { 
     for (List<Element> sequence : generateAllPermutations(input - first)) 
      output.add(first + sequence); 
    } 
}