algorithm - 特定の値のセットのすべての順列を一覧表示する

パフォーマンス、特定の分散、シンプルさから選択できます。特定の分布とは、出力の辞書式などの特定の順序に関心があるかどうかです。

私の知る限り最も効果的なアルゴリズムは、Steinhausアルゴリズムです。 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 の対数です ;再帰呼び出しスタックの深さも対数であるため、O（n.log（n）.log（n）） パフォーマンスの見積もりは次のとおりです。

（このアルゴリズムは、適切に動作するランダム置換ジェネレーターへの変換にも適しています。）

本当に良いリソースを見つけました。 それがあなたを助けることを願っています。

この質問は既に質問され、回答されています（実際には何度も）。

リストのすべての可能な順列を生成するアルゴリズム？

与えられた整数の順列

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

最も単純な実装のJavaのような擬似コード：