アルゴリズムおすすめ本の覚書とフィッシャー–イェーツのシャッフルのサンプルコードです。
目次
アルゴリズムおすすめ本(C言語、JavaScript)
昔の名作が改訂されていました。
ポチップ
今はこんな本もでているんですね。
ポチップ
フィッシャー–イェーツのシャッフルの本もありました。
ポチップ
スポンサーリンク
【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;
}const shuffled = [...array];:- 受け取った配列
arrayをshuffledという新しい配列にコピーしています。 ...arrayはスプレッド構文を使って配列の要素を展開しています。- これにより、
arrayと同じ要素を持つ新しい配列shuffledが作られます。
- 受け取った配列
for (let i = shuffled.length - 1; i > 0; i--) {:- ループ変数
iを初期化し、shuffled配列の最後のインデックスから開始します。 - ループは
iが0より大きい間繰り返されます。 i--により、ループごとにiの値が1ずつ減少します。マイナスなので注意しましょう。
- ループ変数
const j = Math.floor(Math.random() * (i + 1));:- ランダムな整数値
jを生成します。 Math.random()は0以上1未満の乱数を返す関数です。(i + 1)を乗算することで、乱数の範囲を0からiまでの整数に拡大します。+1するのは配列が0からはじまるからです。Math.floor()により、小数部分を切り捨てて整数にします。
- ランダムな整数値
[shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]];:- 配列の要素を入れ替えるためのスワップ処理を行います。
shuffled[i]とshuffled[j]の値を交換します。- 配列の要素を交換するために、分割代入（Destructuring Assignment）を使っています。
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のアルゴリズムは以下の特徴を持っています:
- 各要素が一度だけシャッフルされます。
- シャッフルされた結果は均等な確率で得られます。
本もでています。
ポチップ
スポンサーリンク
モジュロ演算子のループ処理
シャッフルではなく、カウンターを順番にループさせたい場合、モジュロ演算子のループ処理が便利です。
(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…と循環します。
コメント