`std::next_permutation` アルゴリズムはどのように機能するのでしょうか?また、変数 `i`、`j`、および `k` は何を表しますか?

std::next_permutation 実装の説明

質問:

はどのように機能しますか? std::next_permutation アルゴリズムは機能しますか?変数 i、j、および k は何を表しますか?また、それらの値は実行中にどのように変化しますか?

コンセプト:

std::next_permutation を理解するには、要素で表される桁を含む数値として順列を表示します。目標は、次の順列を「昇順」で生成し、数値の増加量を最小限に抑えることです。

コア ループ:

の中心部アルゴリズムには while ループがあります:

while (true) {
    It j = i;
    --i;

    if (*i < *j) {
        // ...
    }

    if (i == begin) {
        // ...
    }
}

このループは、最後の要素から最初の要素まで逆方向に反復されます。重要な洞察は、右側のすべてが降順である場合にのみ、数字の位置を変更する必要があるということです。

左端の降順シーケンスの検索:

If i と j が指す要素は昇順ですが、一番左の降順シーケンスが見つかりました。

入れ替えと並べ替え:

一番左の降順シーケンスを見つけたら、i が指す数字をその右側の「次に大きい」数字と交換します。この数字は、末尾から反復して i より大きい数字が見つかったときに停止することで識別されます。

交換後、右側の残りの数字はすでに降順になっているため、単にそれらを逆にして、次の順列を取得します。

特定の変数:

• i: 降順シーケンスの左端の要素へのポインター。
• j: i の右側の要素へのポインタ。
• k: 要素へのポインタ。 i の右側で、i のすぐ大きい値です。

以上が`std::next_permutation` アルゴリズムはどのように機能するのでしょうか?また、変数 `i`、`j`、および `k` は何を表しますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。