長さ n の順列は、番号 1、2、...、n の繰り返しのない順序付けられたコレクションです。たとえば、[3, 1, 2] と [5, 4, 3, 2, 1] は順列ですが、[1, 2, 1, 3] と [1, 2, 4] は順列ではありません。
長さ n のすべての順列を反復処理する必要があるという事実にタスクが縮小された場合、「next_permutation」と呼ばれる C++ の便利なメカニズムを使用できます。
詳細についてはドキュメントを参照してください。ただし、要点は、この関数が渡された配列を変更することです。辞書式順序での後続の順列 (一般的に明確であり、その名前) に。
next_permutation を使用するには、アルゴリズム ライブラリを含める必要があります (つまり、プログラムの先頭に #include <algorithm> を記述します)。
例:
vector arr;
arr = { 1, 2, 3 }; // 配列は [1, 2, 3] です
next_permutation(arr.begin(), arr.end()); // 配列全体を関数に渡す
// 配列は [1, 3, 2] になりました
arr = { 2, 3, 1 }; // 配列は [2, 3, 1] です
next_permutation(arr.begin(), arr.end()); // 配列全体を関数に渡す
// 配列は [3, 1, 2] になりました
next_permutation(arr.begin() + 1, arr.begin() + 3); // 配列の一部に関数を適用することは可能ですが、実際にはほとんど必要ありません
// 配列は [3, 2, 1] になりました
この場合、関数は、次の順列が生成された場合は true であり、次の順列が存在しなかった場合は false であるブール値の戻り値を持ちます (辞書順で最大の順列が関数に渡される場合)。
これにより、関数をループで使用できるようになり、すべての順列を一度に反復処理できるようになります。順列には正式には 1 から n までの数値が含まれますが、0-indexing により、実際には、0 から n - 1 までの数値の順列を使用する方が便利なことがよくあります。しかし幸いなことに、これによってコードに追加のオーバーレイが発生することはありません。 next_permutation 関数は、インデックスが 0 の順列に適合しています (配列内の重複要素にも対応していますが、詳細は自分で調べることができます)。
一般に、すべての順列を繰り返すコードは次のようになります。
intn; // 順列サイズ
vectorperm(n); // perm は「順列」の略です。つまり、 "順列"
for (int i = 0; i < n; i++)
perm[i] = 私; // 初期順列 0, 1, ..., n - 1 を初期化します
する {
// ループ内で現在の順列を処理します
while (next_permutation(perm.begin(), perm.end())); // 次の順列がない場合は、ループを終了します
このコードは O(n! * f(n)) で実行されます。ここで、f(n) は 1 つの特定の順列を処理するのにかかる時間です。