ダステンフェルドのシャッフルについてのメモ

ダステンフェルドの手法

要素数が n の配列 a をシャッフルする(添字は0からn-1):
  in - 1 から 1 まで減少させながら、以下を実行する
       j に 0 以上 i 以下のランダムな整数を代入する
       a[j] と a[i]を交換する

例)数字の「1,2,3,4,5」をシャッフルする場合の手順

1.数字を基準とするやり方。どこにあるか位置は関係なし。

(1)「数字の5」と「数字の1~5のどれか」を交換する

(2)「4」と「1~4のどれか」を交換する

(3)「3」と「1~3のどれか」を交換する

(4)「2」と「1~2のどれか」を交換する

あるいは、以下の処理でも同じ。

2.位置を基準とするやり方。数字は何であるか関係なし。

(1)「5番目にある数」と「1~5番目にある数」のどれかを交換する

(2)「4番目」と「1~4番目」のどれかを交換する

(3)「3番目」と「1~3番目」のどれかを交換する

(4)「2番目」と「1~2番目」のどれかを交換する 

プログラミングでの処理は↑こちら。

紙でやってみる。順序は違うが結果は同じになる。