![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?5a7ff87)
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ベストアンサー
- 回答日時:
「入れ替えている」と考えるからおかしく感じているんだと思います。
このアルゴリズムは「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
- 回答日時:
実際に入れ替えている
my $j = int rand ($i+1);
@$deck[$i,$j] = @$deck[$j,$i];
をみればわかるように、二つの要素が存在してなければこの操作は意味がありません。つまり、
--$iがゼロになるとき(対象の要素がひとつのとき)はループ本体を実行しないでいいということです。
>$j が偶然 0 になることは有り得ますが、確実に 0 になるわけではなく、確率的に偏ってしまうようなことはないのでしょうか ?
そんなに心配なら数学カテゴリにいって、専門家に訊いてみるとよいと思います。
全く仰る通りです。完全に見当違いでした。
更に、$j が必ず $i 以下の添え字を指して居るので確率的にも偏らない事を確認しました。
御手数御掛けして仕舞い申し訳有りません。御回答有難う御座いました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# c言語の問題です 課題1 (二分探索木とセット) 大きさ size の配列 array を考える。す 2 2023/01/10 21:08
- C言語・C++・C# C言語の課題が出たのですが自力でやっても分かりませんでした。 要素数がnであるint型の配列v2の並 3 2022/11/19 17:41
- C言語・C++・C# カードシャッフルのブログラムを使ってc言語でブラックジャックをしたい 2 2022/04/12 15:13
- PHP 配列の値の更新方法について 1 2022/08/05 09:49
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- C言語・C++・C# C言語初心者 ポインタについて、お助けください、、 2 2023/03/15 23:50
- Visual Basic(VBA) Vbaで数式をポーランド記法に変換するコードを作って実行しようとするとフリーズします。 1 2022/05/24 17:53
- 占い おすすめのタロット/オラクル/ルノルマンカードを探しています 1 2022/09/10 10:02
- Perl perlをバージョンアップしたら、今まで正常に動いていたプログラムが、エラーになってしまった 3 2022/10/05 15:44
関連するカテゴリからQ&Aを探す
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
変数名(配列)の中の変数
-
if文条件式で配列を使用したい
-
perl このテキストファイルを簡...
-
VBAのautofilter、criteriaの配...
-
perl 配列名変数指定するには
-
newで個別に生成した配列にNULL...
-
英語でのシャープとコメの呼び...
-
UWSCの終了の仕方
-
pythonでファイルのコメント行...
-
プログラミングについて。 1つ...
-
javaのループ処理の結果を足し...
-
OSもどきを作りたいです(OSで...
-
画面を強制的に再描画させる方法
-
VBA for文が止まらない
-
非共通要素を抜き出す
-
ネットワークループとルーティ...
-
CASL2のアセンブリ(?)で質問...
-
うるう年判定のアルゴリズム
-
C言語の関数ポインタのイメージ...
-
VBA エクセル2010 横長データ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
VBAのautofilter、criteriaの配...
-
Strawberry Perl for Windows ...
-
リストボックスに縦スクロール...
-
二次元配列のインデックスについて
-
文字の整列(printf)
-
エクセルVBAでTransposeの不思議
-
クラスに配列を渡す方法
-
二次元配列における要素数のは...
-
Excel VBA ユーザーフォームの...
-
perlで配列の要素が空なのを知...
-
perlで2次元配列をサブルーチ...
-
マクロ Publicでの配列定義
-
Dim flag(4) as boolean で配列...
-
参照配列の要素数の求め方は?
-
チェックボックスのperlでの値...
-
VB6で配列の最大値を簡単に求め...
-
jcode->jfold で禁則処理
-
DataGridViewに配列の値を表示...
-
VBScript 配列
-
配列を使わずに、数字(連番)...
おすすめ情報