22

この単純なシャッフル アルゴリズムでは偏った結果が生成されるようです。

# suppose $arr is filled with 1 to 52

for ($i < 0; $i < 52; $i++) { 
  $j = rand(0, 51);

  # swap the items

  $tmp = $arr[j];
  $arr[j] = $arr[i];
  $arr[i] = $tmp;
}

試してみてください... 52 を使用する代わりに 3 を使用し (3 枚のカードのみを使用すると仮定)、10,000 回実行して結果を集計すると、結果が特定のパターンに偏っていることがわかります...

問題は...それが起こるという簡単な説明は何ですか？

正しい解決策は、次のようなものを使用することです

for ($i < 0; $i < 51; $i++) {  # last card need not swap 
  $j = rand($i, 51);        # don't touch the cards that already "settled"

  # swap the items

  $tmp = $arr[j];
  $arr[j] = $arr[i];
  $arr[i] = $tmp;
}

しかし問題は...なぜ最初の方法も完全にランダムに見えるのに、結果が偏ってしまうのでしょうか?

更新 1:正しくシャッフルするには rand($i, 51) である必要があると指摘してくださった方々に感謝します。

4

12 に答える 12

38

これを参照してください：
ナイーブの危険性（コーディングホラー）

例として、3 枚のカード デッキを見てみましょう。3 枚のカード デッキを使用する場合、シャッフル後のデッキの可能な順序は 6 つだけです。 123, 132, 213, 231, 312, 321.

最初のアルゴリズムでは、rand()さまざまなポイントでの関数の結果に応じて、コードに 27 の可能なパス (結果) があります。これらの結果はそれぞれ、同じように発生する可能性があります (偏りはありません)。これらの結果のそれぞれは、上記の 6 つの可能な「実際の」シャッフル結果のリストから同じ単一の結果にマップされます。これで、27 個のアイテムとそれらを入れる 6 個のバケットができました。27 は 6 で割り切れないため、これらの 6 つの組み合わせの一部は過剰に表現されている必要があります。

2 番目のアルゴリズムでは、6 つの可能な「実際の」シャッフル結果に正確に対応する 6 つの可能な結果があり、それらは時間の経過とともにすべて等しく表現される必要があります。

最初のアルゴリズムで過剰に表現されるバケットはランダムではないため、これは重要です。バイアス用に選択されたバケットは、再現可能で予測可能です。 したがって、オンライン ポーカー ゲームを構築しているときに最初のアルゴリズムを使用すると、ハッカーはナイーブ ソートを使用したことを突き止め、その結果、特定のデッキ アレンジメントが他のデッキ アレンジメントよりも発生する可能性がはるかに高いことが判明する可能性があります。その後、彼らはそれに応じて賭けをすることができます。彼らはいくらかを失いますが、失うよりもはるかに多くを勝ち取り、すぐに廃業に追い込みます。

于 2009-05-13T17:21:00.213 に答える
26

これらの置換の完全な確率ツリーは次のとおりです。

シーケンス 123 から開始すると仮定して、問題のコードでランダムな結果を生成するさまざまな方法をすべて列挙します。

123
 +- 123          - swap 1 and 1 (these are positions,
 |   +- 213      - swap 2 and 1  not numbers)
 |   |   +- 312  - swap 3 and 1
 |   |   +- 231  - swap 3 and 2
 |   |   +- 213  - swap 3 and 3
 |   +- 123      - swap 2 and 2
 |   |   +- 321  - swap 3 and 1
 |   |   +- 132  - swap 3 and 2
 |   |   +- 123  - swap 3 and 3
 |   +- 132      - swap 2 and 3
 |       +- 231  - swap 3 and 1
 |       +- 123  - swap 3 and 2
 |       +- 132  - swap 3 and 3
 +- 213          - swap 1 and 2
 |   +- 123      - swap 2 and 1
 |   |   +- 321  - swap 3 and 1
 |   |   +- 132  - swap 3 and 2
 |   |   +- 123  - swap 3 and 3
 |   +- 213      - swap 2 and 2
 |   |   +- 312  - swap 3 and 1
 |   |   +- 231  - swap 3 and 2
 |   |   +- 213  - swap 3 and 3
 |   +- 231      - swap 2 and 3
 |       +- 132  - swap 3 and 1
 |       +- 213  - swap 3 and 2
 |       +- 231  - swap 3 and 3
 +- 321          - swap 1 and 3
     +- 231      - swap 2 and 1
     |   +- 132  - swap 3 and 1
     |   +- 213  - swap 3 and 2
     |   +- 231  - swap 3 and 3
     +- 321      - swap 2 and 2
     |   +- 123  - swap 3 and 1
     |   +- 312  - swap 3 and 2
     |   +- 321  - swap 3 and 3
     +- 312      - swap 2 and 3
         +- 213  - swap 3 and 1
         +- 321  - swap 3 and 2
         +- 312  - swap 3 and 3

ここで、4 番目の列 (スワップ情報の前の列) には、27 の可能な結果を​​持つ最終結果が含まれています。

各パターンが発生する回数を数えましょう。

123 - 4 times
132 - 5 times
213 - 5 times
231 - 5 times
312 - 4 times
321 - 4 times
=============
     27 times total

無作為にスワップするコードを無限回実行すると、パターン 132、213、および 231 がパターン 123、312、および 321 よりも頻繁に発生します。これは、単純に、コードがスワップする方法によって発生する可能性が高くなるためです。 .

もちろん、コードを 30 回 (27 + 3) 実行すると、すべてのパターンが 5 回発生する可能性があると言えますが、統計を扱う場合は、長期的な傾向を調べる必要があります。

考えられる各パターンのランダム性を調べる C# コードを次に示します。

class Program
{
    static void Main(string[] args)
    {
        Dictionary<String, Int32> occurances = new Dictionary<String, Int32>
        {
            { "123", 0 },
            { "132", 0 },
            { "213", 0 },
            { "231", 0 },
            { "312", 0 },
            { "321", 0 }
        };

        Char[] digits = new[] { '1', '2', '3' };
        Func<Char[], Int32, Int32, Char[]> swap = delegate(Char[] input, Int32 pos1, Int32 pos2)
        {
            Char[] result = new Char[] { input[0], input[1], input[2] };
            Char temp = result[pos1];
            result[pos1] = result[pos2];
            result[pos2] = temp;
            return result;
        };

        for (Int32 index1 = 0; index1 < 3; index1++)
        {
            Char[] level1 = swap(digits, 0, index1);
            for (Int32 index2 = 0; index2 < 3; index2++)
            {
                Char[] level2 = swap(level1, 1, index2);
                for (Int32 index3 = 0; index3 < 3; index3++)
                {
                    Char[] level3 = swap(level2, 2, index3);
                    String output = new String(level3);
                    occurances[output]++;
                }
            }
        }

        foreach (var kvp in occurances)
        {
            Console.Out.WriteLine(kvp.Key + ": " + kvp.Value);
        }
    }
}

これは以下を出力します:

123: 4
132: 5
213: 5
231: 5
312: 4
321: 4

したがって、この答えは実際には重要ですが、純粋に数学的な答えではありません。ランダム関数が進む可能性のあるすべての方法を評価し、最終的な出力を確認する必要があります。

于 2009-05-13T20:18:27.660 に答える
22

他の回答に対するあなたのコメントから、分布が一様分布ではない理由の説明(割り切れる答えは単純なもの) だけでなく、それがなぜであるかの「直感的な」説明も探しているようです。実際には均一にはほど遠い。

ここに一つの見方があります。最初の配列[1, 2, ..., n](n は 3 か 52 など) から始めて、2 つのアルゴリズムのいずれかを適用するとします。すべての順列の可能性が一様である場合、1 が最初の位置に留まる確率は になります1/n。実際、2 番目の (正しい) アルゴリズムでは 1/n、1 がその場所にとどまるのは、それが最初にスワップされない場合、つまり への最初の呼び出しrand(0,n-1)が 0 を返す場合のみです
。ただし、最初の (間違った) アルゴリズムでは, 1 は、それが最初にも他の時間にもスワップされない場合にのみ変更されません — つまり、最初に0が返され、他のいずれも返されない場合にのみrandrands は 0 を返します。その確率は (1/n) * (1-1/n)^(n-1) ≈ 1/(ne) ≈ 0.37/n であり、1/n ではありません。

これが「直感的な」説明です。最初のアルゴリズムでは、初期のアイテムは後のアイテムよりも場所がずれて交換される可能性がはるかに高いため、得られる順列は、初期のアイテムが元の場所にないパターンに偏っています。

(それよりも少し微妙です。たとえば、1 が後の位置にスワップされ、一連の複雑なスワップによって元の位置に戻される可能性がありますが、これらの確率は比較的重要ではありません。)

于 2009-05-13T20:52:10.693 に答える
15

この効果について私が見た最も良い説明は、CodingHorrorブログ ( The Danger of Naiveté ) の Jeff Atwood によるものでした。

このコードを使用して、3 枚のカードのランダム シャッフルをシミュレートします...

for (int i = 0; i < cards.Length; i++)
{
    int n = rand.Next(cards.Length);
    Swap(ref cards[i], ref cards[n]);
}

...このディストリビューションを取得します。

3カードシャッフルの配布

シャッフル コード (上記) により、3^3 (27) 通りのデッキの組み合わせが可能になります。しかし、数学は、実際には 3 つしかないことを示しています。または 3 カード デッキの 6 つの可能な組み合わせ。そのため、一部の組み合わせは過剰に表現されています。

カードのデッキを適切に (ランダムに) シャッフルするには、 Fisher-Yates シャッフルを使用する必要があります。

于 2009-05-13T17:21:53.440 に答える
3

もう 1 つの直感は次のとおりです。少なくとも 2 方向の対称性が既に存在しない限り、単一のシャッフル スワップでは、ポジションを占有する確率に対称性を作成できません。3 つの位置 A、B、C を呼び出します。ここで、カード 2 が位置 A にある確率を a、カード 2 が位置 B にある確率を b、位置 C にある確率を c とします。スワップ移動に。a!=b、b!=c、c!=a というように、同じ確率は 2 つとないとします。次に、スワップ後にカードがこれら 3 つの位置にある確率 a'、b'、および c' を計算します。このスワップの動きは、ポジション C が 3 つのポジションのうちの 1 つとランダムにスワップされることで構成されているとしましょう。それで：

a' = a*2/3 + c*1/3
b' = b*2/3 + c*1/3
c' = 1/3.

つまり、カードがポジション A にある確率は、ポジション A がスワップに関与していない時間の 2/3 に、カードがすでにあった確率に、ポジション C にあった確率に 1 を掛けた値です。 /3 C が A と交換される確率など。最初の 2 つの方程式を差し引くと、次のようになります。

a' - b' = (a - b)*2/3

これは、a!=b と仮定したため、a'!=b' であることを意味します (ただし、十分なスワップがあれば、時間の経過とともに差は 0 に近づきます)。しかし、a'+b'+c'=1 であるため、a'!=b' の場合、どちらも c' と等しくないため、1/3 になります。そのため、スワップ前に 3 つの確率がまったく異なる場合、スワップ後もすべて異なります。これは、どの位置がスワップされても保持されます。上記の変数の役割を交換するだけです。

最初のスワップは、位置 A のカード 1 を他のカードと交換することから始まりました。この場合、カード 1 が B の位置にある確率 = カード 1 が C の位置にある確率 = 0 であるため、交換前は双方向の対称性がありました。等しい確率で 3 つの位置のそれぞれに。これは、その後のすべてのスワップに当てはまります。しかし、カード 2 は、最初のスワップ後に確率 (1/3, 2/3, 0) で 3 つの位置に配置され、同様に、カード 3 は確率 (1/3, 0, 2/3) で 3 つの位置に配置されます。 . したがって、その後何回スワップを行っても、カード 2 または 3 が 3 つのポジションすべてを占める確率がまったく同じになることは決してありません。

于 2009-05-13T20:48:32.730 に答える
2

Coding Horror の投稿The Danger of Naïvetéを参照してください。

基本的に（3枚のカードを想定）：

単純なシャッフルでは、33 (27) 通りのデッキの組み合わせが可能です。数学は、実際には 3 つしかないことを示しているため、これは奇妙です。または 3 カード デッキの 6 つの可能な組み合わせ。KFY シャッフルでは、最初の順序で開始し、3 番目の位置から 3 枚のカードのいずれかと交換し、2 番目の位置から残りの 2 枚のカードと再び交換します。

于 2009-05-13T17:34:56.693 に答える
1

簡単な答えは、このアルゴリズムを実行する方法は 52^52 ありますが、52 しかないということです! 52枚のカードの可能な配置。アルゴリズムが公平であるためには、これらの配置のそれぞれを均等に生成する必要があります。52^52 は 52! の整数倍ではありません。したがって、いくつかの取り決めは他の取り決めよりも可能性が高いに違いありません。

于 2009-05-15T01:40:42.427 に答える
1

例示的なアプローチは次のようになります。

1) 3 枚のカードのみを考慮します。

2) アルゴリズムが均等に分散された結果を出すためには、「1」が a[0] になる可能性は 1/3 でなければならず、「2」が a[1] になる可能性も 1/3 でなければなりません。など。

3) 2 番目のアルゴリズムを見ると、次のようになります。

"1" が a[0] で終わる確率: 0 が生成された乱数であるため、(0,1,2) のうち 1 つのケースは、3 つのうち 1 つ = 1/3 です。

"2" が a[1] になる確率: 最初に a[0] にスワップされず、2 回目に a[2] にスワップされなかった場合: 2/3 * 1 /2 = 1/3

"3" が a[2] になる確率: 最初に a[0] にスワップされず、2 回目に a[1] にスワップされなかった場合: 2/3 * 1 /2 = 1/3

それらはすべて完全に 1/3 であり、ここではエラーは見られません。

4) 最初のアルゴリズムで "1" が a[0] になる確率を計算しようとすると、計算が少し長くなりますが、lassevk の回答の図が示すように、9/27 = 1 です。 /3 ですが、「2」が a[1] になる確率は 8/27、「3」が a[2] になる確率は 9/27 = 1/3 です。

その結果、"2" は a[1] として 1/3 ではないため、アルゴリズムはかなり歪んだ結果を生成します (3/10000000000000 = 0.00000000003% などの無視できるケースとは対照的に、約 3.7% のエラー)。

5) Joel Coehoorn が持っている証拠は、いくつかのケースが過剰に表現されることを実際に証明することができます. なぜ n^n なのかという説明は次のとおりだと思います。反復ごとに、乱数が存在する可能性が n 回あるため、n 回の反復後、n^n のケースが発生する可能性があります = 27。この数は割り切れません。 n = 3 の場合、順列の数 (n! = 3! = 6) が均等になるため、一部の結果は過剰に表現されます。それらは 4 回表示される代わりに 5 回表示されるように過剰に表現されているため、1 から 52 の最初の順序で何百万回もカードをシャッフルすると、過剰に表現されたケースは 500 万と表示されます。 400 万回とは対照的に、これは非常に大きな違いです。

6) 過剰表現が示されていると思いますが、「なぜ」過剰表現が起こるのでしょうか?

7) アルゴリズムが正しいかどうかの究極のテストは、任意の数が任意のスロットに到達する確率が 1/n であることです。

于 2009-05-18T09:12:49.100 に答える
0

別の答えが必要というわけではありませんが、Fisher-Yatesが一様である理由を正確に解明しようとする価値があることがわかりました。

N個のアイテムを持つデッキについて話している場合、この問題は次のとおりです。それをどのように示すことができますか

Pr(Item i ends up in slot j) = 1/N?

条件付き確率でそれを分解すると、次のPr(item i ends up at slot j)ようになります

Pr(item i ends up at slot j | item i was not chosen in the first j-1 draws)
* Pr(item i was not chosen in the first j-1 draws).

そこから再帰的に展開して最初の描画に戻ります。

iここで、最初の描画で要素が描画されなかった確率は ですN-1 / N。そして、最初の抽選で描かれなかったという事実を条件として、2番目の抽選で描かれなかった確率はN-2 / N-1、等々です。

iしたがって、要素が最初のj-1描画で描画されなかった確率を取得します。

(N-1 / N) * (N-2 / N-1) * ... * (N-j / N-j+1)

j そしてもちろん、以前に抽選されていないことを条件としてラウンドで抽選される確率は1 / N-j.

最初の項では、分子がすべて後続の分母をキャンセルすることに注意してください (つまり、キャンセル、N-1キャンセル、N-2キャンセルまでずっと、N-j+1だけを残しますN-j / N)。

iしたがって、要素がスロットに現れる全体的な確率jは次のとおりです。

[(N-1 / N) * (N-2 / N-1) * ... * (N-j / N-j+1)] * (1 / N-j)
= 1/N

予想通り。

「単純なシャッフル」についてより一般的に説明すると、欠けている特定の特性は交換性と呼ばれます。シャッフルが作成される方法の「パス依存性」 (つまり、出力を作成するために 27 のパスのどれに従うか) のため、さまざまなコンポーネントごとの確率変数を、任意の順序で出現できるかのように扱うことができません。 . 実際、これはおそらく、無作為抽出において交換可能性が重要である理由の動機付けとなる例です。

于 2014-10-31T13:26:13.567 に答える
0

Naive アルゴリズムは、次のように n の値を選択します。

n = ランド(3)

n = ランド(3)

n = ランド(3)

n の 3^3 通りの組み合わせ

1,1,1, 1,1,2....3,3,2 3,3,3 (27 の組み合わせ) lassevk の回答は、これらの組み合わせのカード間の分布を示しています。

より良いアルゴリズムは次のことを行います。

n = ランド(3)

n = ランド(2)

ん！n の可能な組み合わせ

1,1, 1,2, 2,1 2,2 3,1 3,2 (6 つの組み合わせ、すべて異なる結果が得られます)

他の回答で述べたように、6 つの結果を得るために 27 回試行すると、27 は 6 で割り切れないため、6 つの結果を均等に分配することはできません。27 個のビー玉を 6 つのバケツに入れます。バケツには他のバケツよりも多くのビー玉があります。最善の方法は、バケツ 1 から 6 に 4、4、4、5、5、5 個のビー玉を入れることです。

ナイーブ シャッフルの根本的な問題は、3 枚のカードを完全にシャッフルするのに何度もスワップすることです。2 枚のカードを交換するだけで済みます。入れ替わる可能性。カードを交換し続けると、特定のカードが交換される可能性が高くなります。これらの可能性は、交換の組み合わせの合計が 6 で割り切れる場合にのみ 1/3、1/3、1/3 になります。

于 2009-05-18T16:43:33.823 に答える
0

最初のアルゴリズムが失敗したことを示す最も明確な答えは、問題のアルゴリズムを n のグラフ上の n ステップのマルコフ連鎖として見ることです! n 個の自然数のすべての順列の頂点。アルゴリズムは、ある頂点から別の頂点に遷移確率でホップします。1/n最初のアルゴリズムは、各ホップの遷移確率を示します。n^n 個の経路があり、それぞれの確率は です1/n^n。各頂点に着陸する最終的な確率1/n!は、縮小された割合であるとします。これを達成するには、 または でm/n^n=1/n!割り切れる自然n^n = mn!数のような同じ最終頂点を持つ m 個のパスが必要です。しかし、それは不可能です。それ以外の場合、n は次の場合にのみ割り切れる必要があります。mn^nn!n-1n=2. 矛盾があります。

于 2018-06-27T21:39:45.830 に答える
0

これは、マルコフ連鎖をシャッフルするカードの優れた分析です。ちょっと待って、それはすべて数学です。ごめん。:)

于 2009-05-13T23:50:01.277 に答える