0

今日のラボ セッションで、この質問を受けました。

長さ N の要素 1 ... N - 1 を含むベクトルを想像できます。すべての順列、またはベクトル内の要素の順序を生成するアルゴリズム (体系的な) 方法はありますか。提案された方法の 1 つは、ランダムな要素を交換することでした。以前に生成されたすべての順列が将来の参照のために保存されていれば、これは明らかに機能しますが、これは空間的にも時間的にも非常に非効率的な方法であることは明らかです。

ちなみに、これを行う理由は、そのような要素が許可されていないベクトル内の特別な位置から特別な要素 (たとえばゼロの要素) を削除するためです。したがって、ランダムな方法はそれほどばかげているわけではありませんが、要素の数が多く、可能な順列の数 (「特別な位置」のいずれにも「特別な要素」がないようなもの) を想像してみてください。低い。

N = 5 の場合について、この問題を解決しようとしました。

x = [1, 2, 3, 4, 5]

まず、要素 4 と 5 を交換します。

x = [1, 2, 3, 5, 4]

次に、3 と 5 を入れ替えます。

x = [1, 2, 4, 5, 3]

次に3と4：

x = [1, 2, 5, 4, 3]

当初は、ix と jx の 2 つのインデックスを使用することが可能な解決策になると考えていました。何かのようなもの：

ix = 0;
jx = 0;

for(;;)
{
    ++ ix;

    if(ix >= N)
    {
        ix = 0;
        ++ jx;

        if(jx >= N)
        {
            break; // We have got to an exit condition, but HAVENT got all permutations
        }
    }

    swap elements at positions ix and jx

    print out the elements
}

これは、N = 3 の場合に機能します。ただし、より高い N では機能しません。この種のアプローチは正しい線に沿っていると考えられます。3 つのインデックスが使用される方法に拡張しようとしていましたが、何らかの理由でそれが解決策であると考えています。3 番目のインデックスを使用して、インデックス ix が開始または終了するベクトル内の位置をマークします。しかし行き詰まり、SO コミュニティにアドバイスを求めることにしました。

4

1 に答える 1

2

これを行う 1 つの方法は、最初の文字に対して次のようにすることですe。

  • 次の要素での最初の再帰
  • 次に、 のe2後の各要素についてe:
    • スワップeしてe2
    • 次に、次の要素で再帰します
    • そしてスワップを元に戻す

擬似コード:

permutation(input, 0)

permutation(char[] array, int start)
    if (start == array.length)
        print array

    for (int i = start; i < array.length; i++)
        swap(array[start], array[i])
        permutation(array, start+1)
        swap(array[start], array[i])

この関数のメイン呼び出しでは、最初の位置で各文字を試してから再帰します。後で各スワップを元に戻すため、すべての文字を単純にループするだけで機能します。そのため、再帰呼び出しが戻った後、開始した場所に戻ることが保証されます。

そして、これらの再帰呼び出しごとに、残りの各文字を 2 番目の位置で試します。等々。

Java ライブ デモ。

于 2013-11-28T18:27:20.080 に答える