音楽シャッフルクイズ

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

しない。

以下 N=size。ありえる順列は N! 個。SWAPの全組み合わせは N^N 。よって N^N/N! 通りの組み合わせができれば正しくシャッフルされていると言える (コメントで指摘いただいた通り、「正しくシャッフルされていると言えるためには N^N/N! 通りの組みあわせができなければならない」が正しいです…) が、これは N>=3 で整数ではない。

なぜなら、 N^N/N! が整数になるには 1 から N の全ての n に対して N/n が割り切れなければならないが、 N/N-1 は偶奇の違いから N>=3 で常に割り切れない。

(翌朝追記。ここもひどい… N/N-1 が割り切れないのは偶奇は本質的じゃない。 N が 奇なら 2k+1/2k = 1+1/2k で割り切れない、 N が偶なら 2k/(2k-1) = 1-1/(2k-1) で割り切れない)

正解はたぶん (こちらもコメントで指摘いただいたものの方がはるかに簡潔…) 、

for (i = 1; i < size; i++) {
  int r = random(0, i+1);
  int m = music[i];
  music[i] = music[r];
  music[r] = m;
}

理由。

N-1番目の要素は最後以外にSWAPしないため、 1/N の等確率で全てのマスに配置される。

N-2番目の要素は最後から二番目にSWAPするが、この相手は 1/(N-1) で N-2番目以前の要素に等確率。さらに 1/N の確率で N-1番目要素の SWAP 対象になるため、 1/N で N-1 の要素に行く。他の場所に行く確率はそれぞれ 1/(N-1) に N-1番目の SWAP 対象にならない確率 (N-1)/N をかけた 1/N である。

これ順ぐりに考えていくと全ての要素は 1/N の等確率で全ての要素に配置される、つまりランダムシャッフル。ていうか数学的帰納でキチンと証明しなさいと思った。

追記。数学的帰納でキチンと証明。

(*)「n番目の要素は 1/N の等確率で全ての要素に配置されること」を示す。

i) n番目の要素は i=n の時に始めて SWAP され、この時点で music[0] から music[n-1] に 1/n の等確率で配置される。

ii) i=k (k>n) の時、 n番目要素が 1/k の等確率で music[0] から music[k-1] に配置されていると仮定する。

iii) i=k+1 の時、 (1) 1/(k+1) の確率で n 番目要素との SWAP が起き、この場合 n番目要素は music[k] に移動する。 (2) そうでない場合、 music[0] から music[k-1] に配置されたままであるが、これは k/(k+1) で起きる事象なので、この確率はそれぞれ (1/k)*(k/(k+1)) = 1/(k+1) 。 (1) と (2) を考えあわせると、 music[0] から music[k] までに 1/(k+1) の等確率で n番目要素は配置されることになる。

i),ii),iii) より、数学的帰納法により、 n番目の要素は任意の s (s>n) に対して、 i=s の時に music[0] から music[s-1] に等確率 1/s で配置される。 s=N の場合を考えると、 (*) が証明されている。よって上記アルゴリズムはランダムシャッフル。