c++ - すべての要素がその場所を変更するように配列をシャッフルする方法

Question

すべての配列要素がそれらの位置を変更するように、配列をシャッフルする必要があります。配列が与えられた場合、[0,1,2,3]取得する[1,0,3,2]かどうか[3,2,0,1]は問題ありませんが[3,1,2,0]（2変更されないままであるため）。アルゴリズムは言語固有ではないと思いますが、念のため、C ++プログラムで必要です（std::random_shuffle追加の要件のために使用できません）。

Answer 1

これはどうですか？

1. 0 から arrayLength-1 までの数値を含む配列を割り当てます
2. 配列をシャッフルする
3. インデックスがその値と等しい要素が配列にない場合は、手順 4 に進みます。それ以外の場合は、手順 2 から繰り返します。
4. シャッフルされた配列値を配列のインデックスとして使用します。

Answer 2

For each element e
    If there is an element to the left of e
        Select a random element r to the left of e
           swap r and e

これにより、各値が開始位置にないことが保証されますが、重複がある場合に各値が変更されることは保証されません。

BeeOnRopeは、単純ではあるが、これには欠陥があると指摘しています。リスト [0,1,2,3] が与えられた場合、このアルゴリズムは出力 [1,0,3,2] を生成できません。

Answer 3

非常にランダムになるわけではありませんが、すべての要素を少なくとも 1 つの位置で回転させることができます。

std::rotate(v.begin(), v.begin() + (rand() % v.size() - 1) + 1, v.end());

vが最初にあった場合{1,2,3,4,5,6,7,8,9}、回転後は、{2,3,4,5,6,7,8,9,1}、または{3,4,5,6,7,8,9,1,2}などになります。

配列のすべての要素の位置が変わります。

Answer 4

それがあなたのアプリケーションに合うことを願っています。もう 1 つのコンテナーを用意すると、このコンテナーは "map(int,vector(int))" になります。キー要素にはインデックスが表示され、ベクトルの 2 番目の要素には既に使用されている値が保持されます。

たとえば、最初の要素については、rand 関数を使用して、使用する配列の要素を見つけます。配列のこの要素がこのインデックスに使用されているかどうかをマップ構造で確認します。