フィッシャーとイェーツによるアルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/27 02:05 UTC 版)
「フィッシャー–イェーツのシャッフル」の記事における「フィッシャーとイェーツによるアルゴリズム」の解説
このアルゴリズムのオリジナルの手法は、1938年、フィッシャーとイェーツによって Statistical tables for biological, agricultural and medical research に記述された。このアルゴリズムは紙とペンを使うことを想定しており、ランダム選択には乱数表を用いる。1から N までのランダムな順列を得る基本的な手順を以下に示す。 1 から N までの数字を書く。 まだ消されてない数字の数を数え、1 からその数以下までのランダムな数字 k を選ぶ。 残っている数字から k 番目の数字を消し、別の場所にその数字を書き出す。 すべての数字が消されるまで手順 2, 3 を繰り返す。 手順3で書かれた数列が元の数値からのランダム順列となる。 結果の順列を真にランダムで、かつ偏りがないものにするためには、手順2で抽出される数字もまた真にランダムで、かつ偏りがないものでなければならない。フィッシャーとイェーツは、乱数表から必要な範囲内の数字を選び出す際に、いかなる偏りも避けるようにする方法について注意深く記述している。彼らはまた、1から N までのランダムな数字を選択し、重複した場合は除く、といったシンプルな方法で順列の半分を生成したのち、重複することが多くなるであろう残りの半分を、より複雑なアルゴリズムで生成する方法を示している。
※この「フィッシャーとイェーツによるアルゴリズム」の解説は、「フィッシャー–イェーツのシャッフル」の解説の一部です。
「フィッシャーとイェーツによるアルゴリズム」を含む「フィッシャー–イェーツのシャッフル」の記事については、「フィッシャー–イェーツのシャッフル」の概要を参照ください。
- フィッシャーとイェーツによるアルゴリズムのページへのリンク
