algorithm - 限定シャッフルアルゴリズムを探しています

Question

シャッフルの問題があります。カードのスタックのように、値の配列を完全にシャッフルすることについては、多くのページと議論があります。

私が必要としているのは、配列要素を開始位置から最大で N の場所に一様に移動させるシャッフルです。

つまり、N が 2 の場合、要素 I は最大でも I-2 から I+2 (配列の境界内) の位置にシャッフルされます。

これは、いくつかの単純なソリューションでは扱いにくいことが証明されており、要素の動きに方向性バイアスが生じたり、量が不均一になったりします。

Answer 1

そうです、これはトリッキーです！まず、人為的に非ランダムな結果を作成しないようにするために、さらにいくつかのルールを確立する必要があります。

• 要素は、開始位置に残すことができます。これは、公平なシャッフルの必要な部分であり、シャッフルが N=0 で機能することも保証します。
• N が配列の先頭または末尾からの要素の距離より大きい場合、反対側に移動できます。これを禁止するようにアルゴリズムを微調整することはできますが、それは「一様に」要件に違反することになります。つまり、どちらかの端に近い要素は、中央に近い要素よりも置かれたままになる可能性が高くなります。

これで、実際に問題を解決できます。

1. が配列内の現在のインデックスである範囲i + [-N, N]でランダム値の配列を生成します。i配列の範囲外の値を正規化します (例: -1should becomelength-1およびlengthshould be 0)。
2. 配列内で重複する値のペア (衝突) を探し、それらを再計算します。いくつかのオプションがあります:
   • 互いに衝突しなくなるまで両方の値を再計算します。両方とも他の値と衝突する可能性があります。
   • 他の値と衝突しなくなるまで 1 つだけを再計算します。最初の値はまだ衝突する可能性がありますが、2 番目の値は一意になるはずです。つまり、RNG の呼び出しが少なくなる可能性があります。
   • 衝突ごとに使用可能なインデックスのセットを識別し (たとえば、[3, 1, 1, 0]インデックス2が使用可能)、そのセットからランダムな値を選択し、配列値の 1 つを選択した結果に設定します。これにより、衝突が解決されるまでループする必要がなくなりますが、コードが複雑になり、セットが空の場合に遭遇するリスクがあります。
3. ただし、個々の衝突に対処する場合は、配列内のすべての値が一意になるまでプロセスを繰り返します。
4. 元の配列の各要素を、生成した配列で指定されたインデックスに移動します。

＃2を最適に実装する方法がわからないので、ベンチマークすることをお勧めします。ベンチマークに時間をかけたくない場合は、最初のオプションを使用します。他の最適化は高速かもしれませんが、実際には遅くなる可能性があります。

このソリューションの実行時間は理論上無制限ですが、実際にはかなり迅速に終了するはずです。繰り返しますが、重要な場所で使用する前に、ベンチマークとテストを行ってください。

Answer 2

私が思いついた1つの可能な解決策ですが、それがどれほど「素朴」であるかはわかりません。特に端、特に遠端。

1. フラグの配列を作成します (ブール値) N long (スワップされた要素を表します)

2. 各インデックスで、(flags 配列の最初の要素に従って) 既にスワップされているかどうかを確認します。スワップされている場合は、次に進みます (下記参照)。

3. フラグ配列を回転させ、最初の要素 (この要素を表す) を削除し、新しい「スワップされていない」要素を最後に追加します。ASIDE: これは、特に大きな N の場合、配列の内容を実際に移動する必要がないように、モジュラス配列ルックアップを使用して行うことができます。

4. ループ...

   • 0 から N (または N と現在のインデックスの合計がシャッフルされる配列よりも大きい場合は N 未満) の数値を選択します。
   • 0 の場合、要素はそれ自体とスワップし、次へ移動します。
   • それ以外の場合、その要素がスワップ済みとしてマークされている場合は、ループして再試行します。flags 配列には、選択できる要素、それ自体、および最後の要素の 2 つの要素が常に存在することに注意してください (シャッフルされる配列の末尾に近い場合を除きます)。

5. 現在の要素を選択されたスワップされていない要素と交換し、選択された要素をフラグ配列でスワップ済みとしてマークします。次の要素にループする