>
>http://hyuki.com/d/200510.html#20051020190000
>はなかなか面白かった。
>
>自分のアプローチとしてはちょっとださくて、実際に長さ3で検証しようとして、面倒になったのでプログラムを書いてから、ちゃんとした解答を思いついたとゆー。なのでその順に説明しよう。
>
>まずそのプログラムはこんな感じ。
>
>import Array
import List
arraySwap a i1 i2 = a // [(i1, a ! i2), (i2, a ! i1)]
possibleArrays i a = map (arraySwap a i) [lb..ub]
where (lb, ub) = bounds a
evolve n al = main 0 al
where main i al
| i == n + 1 = al
| otherwise = main (i+1) $ concat $ map (possibleArrays i) al
uniq_c [] = []
uniq_c (x:xs) = (c, x) : uniq_c tl
where (c, tl) = count 1 xs
count n [] = (n, [])
count n l@(y:ys)
| x == y = count (n+1) ys
| otherwise = (n, l)
arrays n = uniq_c $ sort $ map elems $ evolve (n-1) $ [listArray (0, n-1) [0..n-1]]
>
>調べてないので uniq_c 相当のってあったっけ？ あったような気も。まーいーや。ようするにだ、ランダムで分岐しているのをすべての可能性についてリストアップしていって、最後にまとめて出現回数をカウントすると。で、こうなる。
>
>*Main> array 3
[(4,[0,1,2]),(5,[0,2,1]),(5[1,0,2]),(5,[1,2,0]),(4,[2,0,1]),(4,[2,1,0])]
>
>というわけで公平にならない。でもなぜだろうか、というところでようやくピンときた。
>
>問題のアルゴリズムでは、公平に0〜(n-1)のが選ばれて、それとi番目の要素がスワップしている。これがn回繰替えされるから、ようするに長さsizeのリストをシャッフルする場合、ランダムの選択のされかたはsizeのsize乗個あるということになる。
>
>これがシャッフルで公平に分配されれば、正しくシャッフルされることになるのだが、シャッフルのバリエーションは長さがsizeのときはその順列、つまり (size)P(size) = (size)の階乗になる。
>
>で、一般のsizeについて、 (size^size) / (size!) は割切れないことは言うまでもない。ということは公平に分配しようがないわけで、正しくシャッフルされることはありえない。
>
>というのが答え。
>
>ちなみにプログラムしていてわかったことは、この「公平さ」の偏りが、リストが長くなるにつれてどんどん偏っていくということ。上の長さ3の場合は出現頻度の差は1しかないけど、長さ4の場合には最大で8と15でほぼ倍の出現確率、長さ5では16と47だからおおよそ3倍、長さ6だと32と159で5倍ほどの比になる。
>
