[解決済み] std::next_permutation 実装解説

質問

私は、どのように std:next_permutation がどのように実装されているのか気になったので gnu libstdc++ 4.7 バージョンを抽出し、識別子と書式をサニタイズして以下のデモを作成しました。

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

template<typename It>
bool next_permutation(It begin, It end)
{
        if (begin == end)
                return false;

        It i = begin;
        ++i;
        if (i == end)
                return false;

        i = end;
        --i;

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

                if (*i < *j)
                {
                        It k = end;

                        while (!(*i < *--k))
                                /* pass */;

                        iter_swap(i, k);
                        reverse(j, end);
                        return true;
                }

                if (i == begin)
                {
                        reverse(begin, end);
                        return false;
                }
        }
}

int main()
{
        vector<int> v = { 1, 2, 3, 4 };

        do
        {
                for (int i = 0; i < 4; i++)
                {
                        cout << v[i] << " ";
                }
                cout << endl;
        }
        while (::next_permutation(v.begin(), v.end()));
}

期待通りの出力が得られます。 http://ideone.com/4nZdx

私の疑問は どのように機能するのですか？ の意味は何ですか？ i , j と k ? これらは実行の異なる部分でどのような価値を持つのでしょうか？ その正しさの証明のスケッチとは何ですか？

メインループに入る前に、0または1要素のリストの些細なケースをチェックするだけであることは明らかです。 メインループの入口でiは最後の要素を指しており（1つ前の終わりではありません）、リストは少なくとも2つの要素の長さです。

メインループのボディでは何が起こっているのでしょうか？

どのように解決するのですか？

いくつかの並べ替えを見てみましょう。

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
...

ある順列から次の順列に行くにはどうしたらよいのでしょうか。まず、物事を少し違った角度から見てみましょう。 要素を数字、並べ換えを数字と見なすことができます。 . このように問題を見ると 並べ替えを昇順に並べたい。 .

私たちが数字を並べるとき、quot;最小の量だけ数を増やしたいと思っています。たとえば、数を数えるとき、1、2、3、10、...とは数えません。間にまだ4、5、...があり、10は3より大きいですが、3をより小さく増やすことで得られる欠番があるためです。上の例では、次のようになります。 1 は長い間最初の数字として残ります。これは、最後の 3 桁の数字に多くの並べ替えがあり、並べ替えがより少なくなるようにするためです。

では、最終的にどのタイミングで 1 ? 下3桁の順列がもうないとき。

また、下3桁の順列がこれ以上ない場合とは？下3桁が降順のとき。

ああ！これがアルゴリズムを理解する鍵なんですね。 右側のすべてが降順のときだけ、"digit" の位置を変更します。 なぜなら、もし降順でないなら、まだ多くの順列が残っているからです。 (つまり、順列をより少ない量で "increase"することができます)。

それでは、コードに戻りましょう。

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

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

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

ループ内の最初の2行から j は要素であり i はその前の要素です。

次に、要素が昇順の場合、( if (*i < *j) )が何かをします。

その他、全体が降順の場合、( if (i == begin) ) であれば、これが最後の順列となります。

そうでない場合は続行し、j と i は本質的にデクリメントされることがわかります。

私たちは今 if (i == begin) の部分は理解できたので、あとは if (*i < *j) の部分だけです。

これは、「右側がすべて降順のときだけ、数字に何かをする必要がある」という私たちの以前の観測を裏付けるものです。昇順の場合 if ステートメントは本質的に、"右側にあるすべてのものが降順になっている一番左の場所を見つけることです"。

もう一度、いくつかの例を見てみましょう。

...
1 4 3 2
2 1 3 4
...
2 4 3 1
3 1 2 4
...

桁の右側がすべて降順になるとき、次のようになることがわかります。 次に大きな数字を見つけ、それを前に置くと そして 残りの数字を昇順に並べます .

コードを見てみましょう。

It k = end;

while (!(*i < *--k))
    /* pass */;

iter_swap(i, k);
reverse(j, end);
return true;

さて、右側のものは降順なので、quot;次の大きな数字" を見つけるには、最初の3行のコードにあるように、最後から反復すればよいのです。

次に、quot;次に大きい数字(next largest digit")を先頭に入れ替えるために iter_swap() ステートメントを使用して、その桁が次に大きいことが分かっているので、右側の桁はまだ降順であることが分かっており、昇順にするためには、単に reverse() それを