番号のリストが表示されます-セルとで要素を交換するリストのすべての順列を生成する1, 2, ... ,n一連の操作はありますか？入力リストが最初からソートされていない、および/またはリストに繰り返しがある場合の一般的なケースはどうですか？n!-1 swapn!swap (i, j)ij
next_permutation()コンテキスト：2つの要素が交換された場合のスコアがすでにわかっていて、可能なすべての順列をブルートフォース（C ++を使用）したい場合、配列の「スコア」を簡単に計算できるという問題を解決しています。
確かに、それは17世紀のベルリンガーに知られていました。では、組み合わせの歴史についてはどうでしょうか。
Steinhaus Johnson Trotterアルゴリズムを参照するか、最寄りのチェンジリンギンググループに相談してください。
私はあなたの質問の2番目の部分、つまり繰り返しの要素でこれを行うことが可能かどうかについて少し調査しました。答えは、「はい、でもそれほど簡単ではありません」だと思います。さらに、セットで簡単にわかるように、隣接するスワップだけで要素が繰り返されているリストを並べ替えることはできません{0, 0, 1, 1}。ただし、1回のスワップで可能です。
基本的なアプローチは、基本的なチェンジリンギングアルゴリズムを使用することですが、単一の要素ではなく、同一の要素のグループに使用します。同一の要素のグループの場合、リスト0 n-k 1 k（nは基本セットの合計サイズ）のk組み合わせのアルゴリズムが可能である必要があります。そのようなアルゴリズムはたくさんありますが、本当に単純なものは見つかりません。最も簡単な方法は、（大まかに言えば）グループ全体に方向を割り当て、それぞれに方向を割り当てることです。1（Shimon Evenアルゴリズムと同様の方法で）。グループを左に移動すると、左端の要素が前後にスイープします。方向が変わるたびに、正しい次のモバイル要素が1つ進みます。これにより、最終的にグループ全体がリストの右側から左側に移動し、その後、全体の方向が反転して元の構成に戻り、右端の要素がスイープを先導します。
この場合でも方向反転の回数が多いので、上記のアルゴリズムでは順列サイクルを追跡できないかもしれませんが、より洗練されたアルゴリズムを使用してサイクルを生成することは可能だと思います。事実上、各順列（順列の変形）からの可能な単一のスワップによって引き起こされるグラフでハミルトン閉路を探していますが、ハミルトン閉路は存在しますが、グラフがかなり大きい。