ダステンフェルドの手法
要素数が n の配列 a をシャッフルする(添字は0からn-1):
i を n - 1 から 1 まで減少させながら、以下を実行する
j に 0 以上 i 以下のランダムな整数を代入する
a[j] と a[i]を交換する
例）数字の「１，２，３，４，５」をシャッフルする場合の手順
１．数字を基準とするやり方。どこにあるか位置は関係なし。
(1)「数字の5」と「数字の1~5のどれか」を交換する
(2)「4」と「1~4のどれか」を交換する
(3)「3」と「1~3のどれか」を交換する
(4)「2」と「1~2のどれか」を交換する
あるいは、以下の処理でも同じ。
２．位置を基準とするやり方。数字は何であるか関係なし。
(1)「5番目にある数」と「1~5番目にある数」のどれかを交換する
(2)「4番目」と「1~4番目」のどれかを交換する
(3)「3番目」と「1~3番目」のどれかを交換する
(4)「2番目」と「1~2番目」のどれかを交換する
プログラミングでの処理は↑こちら。
紙でやってみる。順序は違うが結果は同じになる。
