私は、与えられたセットのすべての潜在的な順列を生成するために使用できるさまざまなテクニック/アプローチの比較に興味があります。指定された値のすべての並べ替えのリスト
答えて
パフォーマンス、特定の配信とシンプルさを選択できます。特定のディストリビューションでは、出力の辞書編集などの特定の順序を気にするかどうかを意味します。
私の知る限り最良のアルゴリズムは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))のパフォーマンスの予測値が続きます。
(このアルゴリズムはまた、行儀ランダム順列ジェネレータへの変換に適しています。)
辞書編集アルゴリズムとは何ですか?比較のための他のすべてのoes。ご意見ありがとうございます。 – Bober02
@ Bober02 - ここに行きます。 –
この質問が既に尋ねたと(実際には何度も)回答されています
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);
}
}
私は間違っていると思う。再帰的なステップで何をしようとしているのですか: 与えられたSをセットし、S- {a}のすべての順列を生成し、各順列にaを加えます。 これは間違っています。各要素の各要素のどこにでもその要素を入力してください。 – Bober02
@ Bober02:私はあなたに従いません。"私はすべての順列のすべての場所にその要素を入力する必要がありますか?"例:{1,1,1,1,1} ..?それは順列ではありません。 –
- 1. SQL - 特定の値を指定した列で並べ替え
- 2. 指定された並べ替えオプションを使用して2つ以上の "列"(キー)に複数の配列の並べ替えを並べ替え
- 3. 並べ替えの方法配列インデックスで並べ替えられたリスト
- 4. アルファベット順の並べ替えられていないリストを並べ替え
- 5. 並べ替え前と並べ替え後の値のストリーム
- 6. Pythonソート値リスト、値で並べ替え
- 7. Groovyのリストのリストを並べ替え
- 8. 未定義列の並べ替え/並べ替え(LINQ \ Entity Framework)
- 9. 特定の値によるVector3のリストの並べ替え
- 10. リストのリストを並べ替える
- 11. 指定された列のangularjsデータテーブルの並べ替えを無効にする
- 12. C++の選択並べ替えなし並べ替え並べ替えなし
- 13. パンダ並べ替えリストstr.split()
- 14. 選択並べ替え並べ替え
- 15. 並べ替えで並べ替え
- 16. ページ分けされたリストを長さで並べ替え、RoRアプリケーションでアルファベット順に並べ替えます
- 17. Rのリストの並び順を並べ替える:1つのリストを並べ替える「他のリストに応じた値」の値
- 18. 長さで並べ替える前にリストをアルファベット順に並べ替える?
- 19. Collections並べ替えて両方のArrayListを並べ替える
- 20. リスト要素の長さに応じた並べ替えリストR
- 21. Chromeで並べ替えられていないリストのリスト項目を並べ替える
- 22. リンクされたリストを並べ替えるポインタの値を変更する
- 23. Clojureのリストの並べ替え
- 24. Pythonのリストの並べ替え
- 25. リスト内のサブリストの並べ替え
- 26. N個のリストの並べ替え
- 27. 2sxc従業員アプリケーションビジュアルクエリで並べ替えのリストを並べ替え
- 28. 並べ替えリストをSortクラスに渡して並べ替え - C#
- 29. Firebaseの指定された子によるフィルタリングと並べ替え
- 30. 指定されたプロパティを使用してオブジェクトの一般的なリストをアルファベット順に並べ替えます。
可能重複した[アルゴリズムは、リストのすべての可能な順列を生成するには?](http://stackoverflow.com/questions/2710713/アルゴリズムから生成可能なすべての可能な順列) – Tacet