random shuffle - やねうらおブログ(移転しました)

結城先生(id:hyuki)がrandom shuffleに関するクイズを出している。*1
http://www.hyuki.com/d/200510.html#i20051020190000

よく初心者にありがちな正しくないrandom shuffleのプログラムだ。これが正しくないことは、以下のように証明できる。*2

(証明)
size = Nと置く。シャッフルの順列組み合わせはN!。SWAPの組み合わせは $N^{N}$ 。均等にshuffleされるためには、後者を前者で割ったものが整数でなければならない。*3

すなわち $\frac{N\cdot N\cdots N}{1\cdot 2\cdots(N-1)\cdot N}$ が整数でなければならない。そのためには、(その分母からいくらかの項を削除した) $\frac{N\cdot N\cdots N}{(N-1)}$ が整数でなければならない。

ところが、NはN-1で割り切れない。なぜなら $\frac{N}{N-1} = 1+\frac{1}{N-1}$ と変形でき、 $N \ge 3$ においてこれは整数ではない。

よって必要条件を満たさないので、正しいrandom shuffleとは言えない。

*2:id:shinichiro_h:20051020#1129820031さんの証明をベースにさせてもらった。

*3:この説明は、id:seamlessbias:20051020#1129827729がわかりやすい。