プログラミング学習

アルゴリズムおすすめ本!配列をランダムに入れ替えるフィッシャー–イェーツのシャッフル!

プログラミング学習

アルゴリズムおすすめ本の覚書とフィッシャー–イェーツのシャッフルのサンプルコードです。

アルゴリズムおすすめ本(C言語、JavaScript)

昔の名作が改訂されていました。

今はこんな本もでているんですね。

フィッシャー–イェーツのシャッフルの本もありました。

著:森 巧尚(著), 著:まつむらまきお(イラスト)
¥2,465 (2023/05/26 21:50時点 | Amazon調べ)
スポンサーリンク

【JavaScript】配列をシャッフルするランダムアルゴリズム

シャッフルする方法です。要素がオブジェクトの配列でもできます。

// 配列をランダムな順序に並び替える関数
function shuffleArray(array) {
  const shuffled = [...array];
  for (let i = shuffled.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]];
  }
  return shuffled;
}
  1. const shuffled = [...array];:
    • 受け取った配列arrayshuffledという新しい配列にコピーしています。
    • ...arrayはスプレッド構文を使って配列の要素を展開しています。
    • これにより、arrayと同じ要素を持つ新しい配列shuffledが作られます。
  2. for (let i = shuffled.length - 1; i > 0; i--) {:
    • ループ変数iを初期化し、shuffled配列の最後のインデックスから開始します。
    • ループはiが0より大きい間繰り返されます。
    • i--により、ループごとにiの値が1ずつ減少します。マイナスなので注意しましょう。
  3. const j = Math.floor(Math.random() * (i + 1));:
    • ランダムな整数値jを生成します。
    • Math.random()は0以上1未満の乱数を返す関数です。
    • (i + 1)を乗算することで、乱数の範囲を0からiまでの整数に拡大します。+1するのは配列が0からはじまるからです。
    • Math.floor()により、小数部分を切り捨てて整数にします。
  4. [shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]];:
    • 配列の要素を入れ替えるためのスワップ処理を行います。
    • shuffled[i]shuffled[j]の値を交換します。
    • 配列の要素を交換するために、分割代入(Destructuring Assignment)を使っています。
  5. return shuffled;:
    • シャッフルされた配列shuffledを返します。

小数点の切り捨て、切り上げ、四捨五入

Math.floor // 小数点切捨て
Math.ceil // 小数点切上げ
Math.round // 小数点四捨五入
toFixed(0) // 桁数指定で小数点四捨五入

配列のスワップのサンプル

let array = [1, 3, 5, 8];
let i=0;
let j=3;

[array[i], array[j]] = [array[j], array[i]];

console.log(array); // => Array [8, 5, 3, 1]
スポンサーリンク

フィッシャー–イェーツのシャッフル

この方法はフィッシャー–イェーツのシャッフルと言われる定番の方法のようです。

Fisher-Yatesのアルゴリズムは以下の特徴を持っています:

  1. 各要素が一度だけシャッフルされます。
  2. シャッフルされた結果は均等な確率で得られます。

本もでています。

著:森 巧尚(著), 著:まつむらまきお(イラスト)
¥2,465 (2023/05/26 21:50時点 | Amazon調べ)
スポンサーリンク

モジュロ演算子のループ処理

シャッフルではなく、カウンターを順番にループさせたい場合、モジュロ演算子のループ処理が便利です。

(counter + 1) % 3 の計算結果は0から2の範囲の数値を循環する形になります。これは % 演算子(モジュロ演算子)が除算の余りを返すためです。余りは常に除数(ここでは3)より小さいので、この場合の結果は0、1、または2になります。

カウンターが以下のように変化する場合を考えてみてください:

  • 初期状態: counter = 0
  • 1回目の更新: (0 + 1) % 3 = 1 なので counter = 1(3で割っても割れずに1)
  • 2回目の更新: (1 + 1) % 3 = 2 なので counter = 21(3で割っても割れずに2)
  • 3回目の更新: (2 + 1) % 3 = 0 なので counter = 0
  • 4回目の更新: (0 + 1) % 3 = 1 なので counter = 1

このように、 (counter + 1) % 3 の計算結果は0、1、2、0、1、2…と循環します。

コメント

タイトルとURLをコピーしました