std::next_permutation アルゴリズムは、辞書編集的に次に大きいシーケンスの順列を見つけるためにどのように機能するのでしょうか?

std::next_permutation 実装の説明

std::next_permutation アルゴリズムは、指定されたシーケンスの辞書編集的に次に大きい順列を計算します。その実装を理解することは、その動作を理解するために非常に重要です。

アルゴリズムの概要

アルゴリズムは、シーケンスを右から左に反復して、左端の「アセンダー」 (つまり、 、後続要素よりも小さい要素）。アセンダーが見つからない場合は、シーケンスが降順であることを意味します。この場合、シーケンスを逆にして最小の順列を取得します。

それ以外の場合、アルゴリズムはシーケンスの右側にある最小の要素を見つけて続行します。アセンダー (「k」と呼ばれます) の。その後、この要素はアセンダーと交換されます。最後に、アセンダの右側の要素が降順を維持するために反転されます。

変数の役割

• i: を指します。検査されている現在の要素。
• j: i の直前の要素を指します。
• k: シーケンス内の最小の要素を指します。

ループ フロー

ループは、i がシーケンスの先頭 (begin) に到達するまで反復されます。各反復内:

1. i がアセンダーでない場合は、i と j がデクリメントされます。
2. i がアセンダーの場合は、i の右側にある最小の要素が検索されます (k )、それを i と交換し、i の右側のすべてを反転します。

例

シーケンス {1, 2, 4, 3} を考えます。 .

• 反復 1: i は最初は 3 です。j は 2 です。 4 (i
• 反復 2: k は 2 であることがわかります。3 は 2 と交換されます。{1, 3, 4, 2} 。 3 の右側の要素 (4 と 2) が反転されます。 {1, 3, 2, 4}.
• 反復 3: i がデクリメントされ、j がデクリメントされます。 i は現在 2 です。j は 1 です。2
• 反復 4: k は 1 であることがわかります。2 は 1 と交換されます。{1, 2, 4, 3}。 2 の右側の要素 (4 と 3) が反転されます。 {1, 2, 3, 4}.
• 反復 5: i がデクリメントされ、j がデクリメントされます。 i は現在 1 です。j はシーケンスの先頭にあります。アセンダーがもうないので、順序が逆になります。 {4、3、2、1}.

以上がstd::next_permutation アルゴリズムは、辞書編集的に次に大きいシーケンスの順列を見つけるためにどのように機能するのでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。