122

実装方法に興味が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要素の長さです。

メインループの本体で何が起こっているのですか？

4

5 に答える 5

188

いくつかの順列を見てみましょう:

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
...

ある順列から次の順列に移動するにはどうすればよいでしょうか? まず、物事を少し違った角度から見てみましょう。要素を数字として、順列を数字として見ることができます。このように問題を見て、順列/数値を「昇順」で並べたいと思います。

数字を注文するときは、「最小量ずつ増やしたい」と考えています。たとえば、数えるときに 1、2、3、10、... は数えません。間にまだ 4、5、... があるためです。 3 を少しずつ増やします。1上記の例では、最後の 3 つの「桁」の並べ替えが多く、順列が「増加」するため、長い間最初の数字のままであることがわかります。

では、いつ最終的に を「使用」するの1でしょうか? 最後の 3 桁の順列がなくなった場合。
そして、最後の 3 桁の順列がなくなるのはいつですか? 下3桁が降順の場合。

あはは！これは、アルゴリズムを理解するための鍵です。「桁」の位置を変更するのは、右側のすべてが降順の場合のみです。降順 でない場合は、まだ順列が残っているためです(つまり、順列を少しだけ「増やす」ことができます)。 .

コードに戻りましょう。

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;

右側は降順であるため、「次に大きい数字」を見つけるには、コードの最初の 3 行でわかるように、最後から反復する必要があります。

次に、「次に大きい数字」をiter_swap()ステートメントの先頭に入れ替えます。その数字が次に大きいことがわかっているので、右側の数字はまだ降順であることがわかります。昇順で並べると、私たちはそれをしなければreverse()なりません。

于 2012-07-14T11:32:36.110 に答える
45

gcc実装は、辞書式順序で順列を生成します。ウィキペディアはそれを次のように説明しています：

次のアルゴリズムは、指定された順列の後に辞書式順序で次の順列を生成します。指定された順列をインプレースで変更します。

  1. a [k] <a [k+1]となる最大のインデックスkを見つけます。そのようなインデックスが存在しない場合、順列は最後の順列です。
  2. a [k]<a[l]となる最大のインデックスlを見つけます。k + 1はそのようなインデックスであるため、lは明確に定義され、k<lを満たします。
  3. a[k]をa[l]と交換します。
  4. a [k+1]から最後の要素a[n]までの順序を逆にします。
于 2012-07-14T10:56:23.210 に答える
9

他の標準ライブラリ アルゴリズムを使用した完全な実装を次に示します。

template <typename I, typename C>
    // requires BidirectionalIterator<I> && Compare<C>
bool my_next_permutation(I begin, I end, C comp) {
    auto rbegin = std::make_reverse_iterator(end);
    auto rend = std::make_reverse_iterator(begin);
    auto rsorted_end = std::is_sorted_until(rbegin, rend, comp);
    bool has_more_permutations = rsorted_end != rend;

    if (has_more_permutations) {
        auto rupper_bound = std::upper_bound(
            rbegin, rsorted_end, *rsorted_end, comp);
        std::iter_swap(rsorted_end, rupper_bound);
    }

    std::reverse(rbegin, rsorted_end);
    return has_more_permutations;
}

デモ

于 2015-09-21T12:36:05.393 に答える