改良されたアルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/27 02:05 UTC 版)
「フィッシャー–イェーツのシャッフル」の記事における「改良されたアルゴリズム」の解説
フィッシャー–イェーツのシャッフルの改良されたバージョンはコンピュータの使用を想定している。それはリチャード・ダステンフェルドによって1964年に紹介され、ドナルド・クヌースもまたThe Art of Computer Programmingにおいて"Algorithm P"として世に広めた。ダステンフェルド、クヌースともに、著書の初版ではフィッシャーとイェーツの研究については、おそらく気づいていなかったために紹介していない。The Art of Computer Programmingの続版ではフィッシャーとイェーツの業績について言及している。 ダステンフェルドのアルゴリズムとフィッシャー–イェーツのそれには、小さいが決定的な差異が存在する。フィッシャー–イェーツの手法を単純にコンピュータで実装する場合、上記の手順3において、残っている数を数え上げるという不要な時間を要する。対してダステンフェルドの手法では「消す」数字を、残っている数字の中で最後の数字と入れ替え、数列の最後に移動させる。これにより、計算量はフィッシャー–イェーツ版の単純な実装の場合のO(n2)と比べ、O(n)に減少する。この変更により、アルゴリズムは下記のようになる。ここでは0始まりの配列を使用する。 要素数が n の配列 a をシャッフルする(添字は0からn-1): i を n - 1 から 1 まで減少させながら、以下を実行する j に 0 以上 i 以下のランダムな整数を代入する a[j] と a[i]を交換する パラメータ p, q に対して p 以上 q 未満のランダムな整数を返す乱数生成器を使用する場合、配列を上記の例と反対方向に走査する以下のアルゴリズムを用いることができる。 要素数がnの配列aをシャッフルする(添字は0からn-1): i を 0 から n - 2 まで増加させながら、以下を実行する j に i 以上 n 未満のランダムな整数を代入する a[j] と a[i]を交換する
※この「改良されたアルゴリズム」の解説は、「フィッシャー–イェーツのシャッフル」の解説の一部です。
「改良されたアルゴリズム」を含む「フィッシャー–イェーツのシャッフル」の記事については、「フィッシャー–イェーツのシャッフル」の概要を参照ください。
- 改良されたアルゴリズムのページへのリンク
