こう立て続けに出題されると睡眠時間が…(ぉ．
んーと，答え自体はわりとすぐ出るのですが，どうもきれいに説明できません．というわけであまりきれいでない説明を書いてみます．自分でも微妙かなと思ってるので送ってません．
(解答編が発表になったので，ネタバレ反転処理をやめました)
答え: 正しくシャッフルはされません．
理由: どんなものでもいいから反例を一つ示せばよいわけで，だから，どれだけきれいにまとめられるかが勝負の分かれ目なわけですね (何の勝負だ)．あまりきれいなものが思いつかなかったけど，とりあえずこんな感じで:
3 曲の場合を考えます．3 曲の順列は 3×2×1 = 6 通りなので，あらゆる順列がすべて等確率で得られるためには，どの順列が生成される確率も 1/6 でなくてはなりません．
さて，関数 shuffle による配列の並び方の遷移を考えると 3×3×3 = 27 通りに分岐する樹系図がかけて，その葉のそれぞれが等しく確からしいといえます．よって任意の順列を考えると，それが生成される確率は m/27 (m は 0 以上の整数) と書けなくてはなりません．
よって m/27 = 1/6 を満たす必要がありますが，これを満たす m = 27/6 は整数ではありません．証明終．
うーん，いまいち．
(2005-10-25 追記) というわけで他の皆さんの解答を読んでみたけど，方向性はほとんど同じみたい．そうか，「n は n-1 では割り切れない」を使えば配列サイズ n = 3 に限らず議論できたわけだ．なるほど． (と思ったら，実はそれではちょっとまずいみたい → [2005-10-26-2])
しかし，もっといろんなアプローチの証明が出て来るかと思っていたけど，皆行き着くところは同じなんだな．ちょっと意外だった．
最終更新時間: 2009-01-04 15:31