4

前の順列と次の順列の違いを把握するために、サンプルプログラムを試していました。しかし、私のプログラムは正しく動作していないようです。配列内の要素の数を尋ねることからプログラムを開始し、単純なforループを使用して配列を構築します

for(i = 0; i < x; i++)
        ptr[i] = i;

cout << "Possible permuations using prev_permutation: " << endl;
    do{
        for(i = 0; i < x; i++)
            cout << ptr[i] << " ";
        cout << endl;
    } while(prev_permutation(ptr, ptr+x));

cout << "Possible permuations using next_permutation: " << endl;
do{
    for(i = 0; i < x; i++)
        cout << ptr[i] << " ";
    cout << endl;
} while(next_permutation(ptr, ptr+x));

3つの要素（0、1、2）のサンプルを使用してコードを実行すると。prev_permutationは私に（0、1、2とそれだけ）を与えます。次に、next_permutationは私に（2、1、0）を与えます。ただし、prev_permutation部分のコードにコメントを付けると、next_permutationのみが実行されているときに、セット（0、1、2）の適切な6つの異なる順列が取得されます。何が起こっているのか理解できないようです。

4

2 に答える 2

8

prev_permutationそしてnext_permutation、辞書式（「アルファベット順」）の順序ですべての順列を生成しfalse、サイクルが完了すると（つまりprev_permutation、最初の順列を呼び出しnext_permutationた後、または最後の順列を呼び出した後）、それらは戻ります。

何が起こるかというと、辞書式順序で最初の順列を使用して配列を準備してから、を呼び出しますprev_permutation。ただし、これが最初であるためprev_permutation、配列を最後の順列に設定して戻り値を返すfalseので、ループを終了します。

ここでnext_permutationループに入りますが、配列の現在の内容は辞書式順序の最後の順列であるため、next_permutation最初の順列を設定し、falseを返します。

ただし、パーツを削除するとprev_permutation、ループnext_permutationは最初から開始されるため、を返す前に6つの順列すべてが正しく生成されfalseます。

順番にリストされているすべての順列を考慮し、現在の構成をこのリストのポインターとして使用して、効果を視覚化できます。

0-1-2 << you start here
0-2-1
1-0-2
1-2-0
2-0-1
2-1-0

電話をかけるnext_permutationときは下に移動し、電話をかけるprev_permutationときは上に移動します。リストの外に出ると、両方の関数がポインタをもう一方の端に移動し、falseこの事実を通知するために戻ります。

prevに移動し2-1-0て関数が戻ることから始めた場合はfalse、を呼び出すnextと関数がに移動して再び0-1-2戻りますfalse。

たとえば、の代わりに0、1および22つのゼロと3つの1の順列を使用すると、辞書式順序は次のようになります。

0-0-1-1-1
0-1-0-1-1
0-1-1-0-1
0-1-1-1-0
1-0-0-1-1
1-0-1-0-1
1-0-1-1-0
1-1-0-0-1
1-1-0-1-0
1-1-1-0-0

したがって、それらすべてを列挙するには、から始めて使用するか、から始めて0-0-1-1-1使用next_permutationする必要が1-1-1-0-0ありますprev_permutation。

この場合next_permutation、最後の呼び出し1-1-1-0-0は最初の呼び出しに変わり、;0-0-1-1-1を返します。false同様の方法で、呼び出しprev_permutationは0-0-1-1-1に変わり、フリップのために1-1-1-0-0戻ります。false

于 2012-09-01T19:39:25.713 に答える
3

両方によって考慮されるすべての順列は、明確に定義された辞書式順序prev_permutationを持っています。あなたが彼らに提供した配列は、その順序でいくつかの位置を持っています。next_permutation

そのため、どちらの関数もすべての順列を提供することが保証されていません。

に最初の可能な順列を指定しprev_permutationた場合、その前に順列はありません。同様に、配列が（2、1、0）として定義されている場合、next_permutation新しい順列は提供されません。

コレクションのすべての順列が必要な場合は、sort最初にコレクションを作成してから、を使用しますnext_permutation。

于 2012-09-01T19:40:07.943 に答える