[ruby-list:41356] 配列のシャッフルのアルゴリズム

原です。

最近また巷で話題（？）の配列のシャッフルの話です。

[ruby-list:40915]での

  array.each_index do |idx|
    jdx = rand(idx + 1)
    array[idx], array[jdx] = array[jdx], array[idx]
  end

というアルゴリズムの正当性についての証明が間違っていたので
正しい証明をもう一度！

-----
今、array = [0, 1, 2, ... , n-1] としておいて、

P(k) = 「array[0...k] までは 0,1,...,k-1 が一様にシャッフルさ
         れ、残り array[k..n-1] は動いていない」

とおきます。全てが始まる前、P(0) は正しいのは明らか。今
P(idx) が正しい、つまり array[0..idx-1] は全ての 0,..,idx-1 
の順列が等確率に現れていると仮定する。このとき、

   jdx = rand(idx + 1)
   array[idx], array[jdx] = array[jdx], array[idx]

がなされた後では、array[0..idx] は 0,..,idx の順列になり、
仮定とスワップのさせ方よりそれぞれの順列は等確率に現れる。

以上より P(idx+1) が正しい。よって、帰納的に P(n) すなわち、
一様にシャッフルされることが証明できた。（証終）
-----

P(k) を設定した時点で殆ど証明は終わっていて、こっちの方が証
明が楽ですね。

前回の証明の間違いとは「一様なシャッフル」の解釈の事で、今回
は「全ての順列が等確率」であることを示したのに対し、前回は
「i が j 番目に来る確率」が全ての i, j について等しいことを
示したのに過ぎなかったのでした。


yts さんの日記

  http://d.hatena.ne.jp/yts/20051022#seeall

を読んで前の証明の間違いに気づきました。「最近話題」というの
は、結城さんの

  http://www.hyuki.com/d/200510.html#i20051023

でクイズとして取り上げられたからです。（[ruby-list:39597] 
でも同様なことが話題になっていました。）