2022-05-04 クヌース・シャッフル（フィッシャー–イェーツのシャッフル）
クヌース・シャッフル（フィッシャー–イェーツのシャッフル）
-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]
Fisher–Yates shuffle - Wikipedia
分布は一様であることの証明
数学的帰納法を使います。
「k 番目のループ（k=0,1,…,n−1）のあと、vec[p] (p∈[0,k]) の値が q∈[0,k] である確率は p,q に関わらずすべて 1/(k+1) である」
という命題を Prop(k) とします。証明したいのは Prop(n−1) です。 Prop(0) は自明です。 Prop(k) を真だと仮定して Prop(k+1) を証明すればいいわけですが、 k+1 番目のループのあとに
- vec[p] (p∈[0,k]) が q∈[0,k] である確率は、 「前回のループ後にその値であった確率」×「今回入れ替えられなかった確率」、 つまり
(1/(k+1))⋅((k+1)/(k+2))=1/(k+2)- vec[p] (p∈[0,k]) が k+1 である確率は、今回入れ替えられた確率、 つまり 1/(k+2)
- vec[k+1] が q∈[0,k+1] である確率はやはり 1/(k+2) というわけで Prop(k+1) が成り立ちます。