指定された値のすべての並べ替えのリスト

Question

私は、与えられたセットのすべての潜在的な順列を生成するために使用できるさまざまなテクニック/アプローチの比較に興味があります。

Answer 1

パフォーマンス、特定の配信とシンプルさを選択できます。特定のディストリビューションでは、出力の辞書編集などの特定の順序を気にするかどうかを意味します。

私の知る限り最良のアルゴリズムはSteinhaus algorithmです。 1つの置換を生成するのに必要なプロセッサ命令の数は一定である（必ずしも必要ではないが、それを印刷するのに必要な命令は含まない）という意味では、乗法定数まで最適である。

非常に単純なアルゴリズムがあり、辞書順に並べ替えることができます。再帰的な手順として再作成することができ、そのパフォーマンスはO（n.log（n）.log（n ））であり、他の方法でリストを生成してソートするのとほぼ同じです。

編集は：ここでは単純なアルゴリズムの擬似コードです：

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メソッドと一緒に、アルゴリズム全体の中で最も高価な操作である再帰呼び出しごとに、セットをコピーして変更することに注意してください。 1組のコピーのコストは、順列の総数で対数である。n;再帰呼び出しスタックの深さも対数であるため、O（n.log（n）.log（n））のパフォーマンスの予測値が続きます。

（このアルゴリズムはまた、行儀ランダム順列ジェネレータへの変換に適しています。）

Answer 2

この質問が既に尋ねたと（実際には何度も）回答されています

Algorithm to generate all possible permutations of a list?

Permutations with a given integer

個人的に私はSteinhausアルゴリズムが問題を過度に考えていると思います。それは最も単純な実装よりもはるかに高速ではありません。最も単純な実装の

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); 
    } 
}