|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ シャッフル ： [しゃっふる] (n) shuffle, (n) shuffle
フィッシャー - イェーツのシャッフルは、有限集合からランダムな順列を生成するアルゴリズムである。簡単に言うならば、集合をランダムにシャッフルする方法である。この名前はロナルド・フィッシャーおよびフランク・イェーツから名付けられた。また、クヌースのシャッフル(ドナルド・クヌースから)とも呼ばれる。フィッシャー - イェーツのシャッフルは、全ての順列の組み合わせが等しく存在しうるため、偏りがない。このアルゴリズムの改良されたバージョンはさらに効果的であり、処理時間はシャッフルされる要素数に比例するのみで、余分な時間はかからず、また追加の保持領域を必要としない。フィッシャー - イェーツのシャッフルの派生にサットロのアルゴリズムがあり、こちらは長さ ''n'' のランダムな円順列を生成する。 フィッシャー - イェーツのシャッフルは、帽子に入れた数字の書かれたくじ（組合せ数学的に区別可能なもの）をなくなるまで取り出して並べていく手順に似ている。 == フィッシャーとイェーツによるアルゴリズム == このアルゴリズムのオリジナルの手法は、1938年、フィッシャーとイェーツ]によって''Statistical tables for biological, agricultural and medical research''に記述された〔 注: 第6版 ISBN 0-02-844720-4 はウェブ上での閲覧が可能となっている 。 しかし記載されているアルゴリズムはによって変更されている。 〕。このアルゴリズムは紙とペンを使うことを想定しており、ランダム選択には乱数表を用いる。1から ''N'' までのランダムな順列を得る基本的な手順を以下に示す。 # 1から ''N'' までの数字を書く。 # まだ消されてない数字の数を数え、1からその数以下までのランダムな数字 ''k'' を選ぶ。 # 残っている数字から ''k'' 番目の数字を消し、別の場所にその数字を書き出す。 # すべての数字が消されるまで手順2,3を繰り返す。 # 手順3で書かれた数列が元の数値からのランダム順列となる。 結果の順列を真にランダムで、かつ偏りがないものにするためには、手順2で抽出される数字もまた真にランダムで、かつ偏りがないものでなければならない。フィッシャーとイェーツは、乱数表から必要な範囲内の数字を選び出す際に、いかなる偏りも避けるようにする方法について注意深く記述している。彼らはまた、1から ''N'' までのランダムな数字を選択し、重複した場合は除く、といったシンプルな方法で順列の半分を生成したのち、重複することが多くなるであろう残りの半分を、より複雑なアルゴリズムで生成する方法を示している。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「フィッシャー - イェーツのシャッフル」の詳細全文を読む スポンサード リンク
|