perlfaq4 で紹介されている Fisher-Yates 法について

質問

perldoc の perlfaq4:
http://perldoc.jp/docs/perl/5.10.0/perlfaq4.pod
の "How do I shuffle an array randomly?" と題された FAQ で紹介されている、配列の要素をシャッフルするアルゴリズム Fisher-Yates 法についての疑問です。

以下一部引用
----------------
sub fisher_yates_shuffle {
my $deck = shift; # $deck is a reference to an array
my $i = @$deck;
while (--$i) {
my $j = int rand ($i+1);
@$deck[$i,$j] = @$deck[$j,$i];
}
}
----------------
以上一部引用

このコードを見ると、まず始めに @$deck の要素数を $i に代入し、次に while ループを使って $i をデクリメントしていき、@$deck の末尾の要素から順番にランダムに並べ替えを行っているようですが、$i を前置デクリメントで評価しているため、配列の先頭の要素すなわち $deck -> [0] は並べ替えられないのではないでしょうか ?

つまり、$deck -> [0] にアクセスするためには -- $i が 0 にならなければならず、もしそうなった場合 while 条件部で偽と判定されるため、ループが実行されないのではないかということです。

-- $i が 1 となる時点では、$j = int rand ($i+1) つまり $j = int rand (2) で、$j は 0 以上 2 未満の整数、0 か 1 になります。
したがって、この場合も確実に $deck -> [0] にはアクセスできません。

もちろん、$j が偶然 0 になることは有り得ますが、確実に 0 になるわけではなく、確率的に偏ってしまうようなことはないのでしょうか ?
おそらく私の見当違いだと思いますが、配列シャッフルのアルゴリズムとして問題ないのでしょうか。ご回答よろしくお願いします。

回答No.2

mtaka2 · ベストアンサー

「入れ替えている」と考えるからおかしく感じているんだと思います。
このアルゴリズムは「1要素ずつランダムに選んで」「後ろから並べていく」というものです。
たとえば、10要素をシャッフルする場合、

$i=9のとき:deck[0～9の乱数]とdeck[9]を入れ替える
　　→10個の要素からランダムに選んだ1つを、配列の一番最後(deck[9])に配置する。
　　以後、deck[9]は変化しない。
　　残るシャッフル対象はdeck[0]～deck[8]の9要素

　　次のループ以降ではdeck[0]～deck[8]からランダムに抽出していくので、この要素間で順番に意味はありません。
　　ですから「ランダムに選んだ1要素を最後に配置する」処理を行う時に「残りの要素の順番」は気にする必要は無いので、
　　「ランダムに選んだ要素」と「最後の要素」の入れ替えで簡単に実現できます。

$i=8のとき:deck[0～8の乱数]とdeck[8]を入れ替える
　　→9要素からランダムに選んだ1つを、配列の最後から2番目(deck[8])に配置する。
　　以後、deck[8]は変化しない。
　　残るシャッフル対象はdeck[0]～deck[7]の8要素
(略)
$i=2のとき:deck[0～2の乱数]とdeck[2]を入れ替える
　　→3要素からランダムに選んだ1つを、配列の最後から8番目(deck[2])に配置する。
　　以後、deck[2]は変化しない。
　　残るシャッフル対象はdeck[0]～deck[1]の2要素

$i=1のとき:deck[0～1の乱数]とdeck[1]を入れ替える
　　→2要素からランダムに選んだ1つを、配列の最後から9番目(deck[1])に配置する。
　　以後、deck[1]は変化しない。
　　残るシャッフル対象はdeck[0]の1要素
　　　　→もうシャッフル操作は不要

という流れになります。

お礼

後ろから並べて行くと言う考え方、非常に参考に成りました。
詳説を頂きまして誠に有難う御座いました。

回答No.1

sakusaker7

実際に入れ替えている
my $j = int rand ($i+1);
@$deck[$i,$j] = @$deck[$j,$i];
をみればわかるように、二つの要素が存在してなければこの操作は意味がありません。つまり、
--$iがゼロになるとき(対象の要素がひとつのとき)はループ本体を実行しないでいいということです。

>$j が偶然 0 になることは有り得ますが、確実に 0 になるわけではなく、確率的に偏ってしまうようなことはないのでしょうか ?

そんなに心配なら数学カテゴリにいって、専門家に訊いてみるとよいと思います。

お礼

全く仰る通りです。完全に見当違いでした。
更に、$j が必ず $i 以下の添え字を指して居るので確率的にも偏らない事を確認しました。
御手数御掛けして仕舞い申し訳有りません。御回答有難う御座いました。