std::next_permutation はどのようにして次の辞書順列の大きい順列を見つけるのでしょうか?

std::next_permutation の仕組み

std::next_permutation は、シーケンスを並べ替える C 標準テンプレート ライブラリ (STL) の関数です。次の辞書編集的により大きな順列に進みます。その実装を理解するには、各要素が数字を表す数値としてシーケンスを視覚化すると役立ちます。

コア ロジック

このアルゴリズムは、次の原則に従って動作します。

• ピボットを見つける: の終わりから開始します。シーケンス内で、その右側の要素 (j) より小さい最初の要素 (i) を見つけます。これは、i の右側の数字が降順であることを示します。
• 入れ替えと反転: i が見つかると、最初の要素 (k) を最後から検索します。私より大きい。この要素は i と交換され、先頭に配置されます。 j の右側 (j から最後まで) の残りの要素が反転されます。
• ピボットをインクリメントします: ピボットが見つかった場合 (i が先頭ではない)、プロセスが繰り返されます。 i と j をデクリメントします。
• 反転して終了: ピボットを実行できない場合見つかった場合 (i が先頭)、順序が逆になり、関数は false を返し、これ以上の置換が不可能であることを示します。

コード内の変数

• i: 一番左のピボットを表しますelement.
• j: i より小さい i の右側の要素を表します。
• k: 右からの要素を表しますそれは i より大きく、次のものと交換されますi.

例

シーケンス 1、3、2、4 を考えます。

• Pivot: i は最初は 4 に設定されていますが、4 はそれ以上であるため、 2 の場合、i = 2 に移動します。2 は 4 より小さいため、i がピボットです。
• スワップとリバース: j は 3 に設定され、k は 1 に設定されます。は、2 より大きい右から最初の要素です。1 と 2 が交換され、結果は 1、2、3、4 になります。j の残りの要素
• Pivot をインクリメントします: i は 1 にデクリメントされます (j はすでに 2 に設定されています)。 。 1 は 2 より小さいため、プロセスが繰り返されます。
• ピボットの検索: i は最初の要素 (先頭) までデクリメントされ、ピボットが見つからないことを示します。
• 反転して終了: シーケンスは元の状態 1、2、に反転されます。 3、4 の場合、関数は false を返し、これ以上の並べ替えは不可能であることを示します。

以上がstd::next_permutation はどのようにして次の辞書順列の大きい順列を見つけるのでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。