Fisher-YatesシャッフルアルゴリズムでJavaScript配列をシャッフルする
JavaScriptで配列をシャッフルする方法
Fisher-Yatesシャッフルアルゴリズムは、最も一般的で効率的なシャッフルアルゴリズムの一つです。このアルゴリズムは、次の手順で実装できます。
function shuffle(array) {
let currentIndex = array.length;
while (currentIndex != 0) {
let randomIndex = Math.floor(Math.random() * currentIndex);
[array[currentIndex - 1], array[randomIndex]] = [array[randomIndex], array[currentIndex - 1]];
currentIndex--;
}
return array;
}
このアルゴリズムは、次のとおり動作します。
currentIndex
変数に配列の長さを代入します。currentIndex
が 0 になるまでループします。randomIndex
変数に、currentIndex
までの範囲のランダムなインデックスを代入します。currentIndex - 1
番目の要素とrandomIndex
番目の要素を入れ替えます。- シャッフルされた配列を返します。
sort()メソッドを利用する方法
JavaScriptの sort()
メソッドを使用して、配列をシャッフルすることもできます。ただし、この方法は非効率的であり、古いブラウザではサポートされていない場合があります。
function shuffle(array) {
return array.sort(() => Math.random() - 0.5);
}
sort()
メソッドを呼び出し、比較関数として匿名関数を渡します。- 匿名関数は、
Math.random()
関数を使用してランダムな値を生成し、0.5 を引き、-1 から 1 までの範囲の値を返します。 sort()
メソッドは、ランダムな値に基づいて配列をソートします。
JavaScriptで配列をシャッフルするには、Fisher-Yatesシャッフルアルゴリズムまたは sort()
メソッドを使用できます。Fisher-Yatesシャッフルアルゴリズムは、より効率的で汎用性が高いため、一般的に推奨されます。
どちらの方法を使用する場合でも、シャッフルされた配列は元の配列とは異なる新しい順序になります。シャッフル操作を繰り返すことで、さまざまな順序の配列を生成できます。
function shuffle(array) {
let currentIndex = array.length;
while (currentIndex != 0) {
let randomIndex = Math.floor(Math.random() * currentIndex);
[array[currentIndex - 1], array[randomIndex]] = [array[randomIndex], array[currentIndex - 1]];
currentIndex--;
}
return array;
}
const numbers = [10, 20, 30, 40, 50];
console.log(numbers); // [10, 20, 30, 40, 50]
const shuffledNumbers = shuffle(numbers);
console.log(shuffledNumbers); // [40, 20, 10, 50, 30] (ランダムな順序)
このコードでは、まず shuffle()
関数を作成します。この関数は、配列を受け取り、シャッフルされた配列を返します。
次に、numbers
という名前の配列を作成し、10 から 50 までの整数を要素として含めます。
最後に、shuffle()
関数を使用して numbers
配列をシャッフルし、結果を shuffledNumbers
変数に格納します。
コンソールに numbers
と shuffledNumbers
を出力すると、numbers
は元の順序で、shuffledNumbers
はランダムな順序であることが確認できます。
このコードを拡張して、さまざまな種類のシャッフルを実装できます。たとえば、次のことができます。
- 特定の要素をシャッフルから除外する
- シャッフルの範囲を制限する
- 特定の順序で要素をシャッフルする
これらの要件を満たすには、shuffle()
関数のロジックを調整する必要があります。
注意点
Fisher-Yatesシャッフルアルゴリズムは、配列内の要素をランダムに並べ替える効率的な方法ですが、完全にランダムな結果を保証するものではありません。これは、アルゴリズムが疑似乱数ジェネレータを使用するためです。
真のランダム性を必要とする場合は、代わりに暗号学的に安全な乱数ジェネレータを使用する必要があります。
このサンプルコードは、JavaScript で配列をシャッフルする方法を示す基本的な例です。さまざまな要件を満たすために、このコードを拡張してカスタマイズできます。
JavaScriptで配列をシャッフルするその他の方法
forループとMath.random()を使う方法
この方法は、Fisher-Yatesシャッフルアルゴリズムよりも単純ですが、少し非効率的です。
function shuffle(array) {
for (let i = array.length - 1; i > 0; i--) {
const randomIndex = Math.floor(Math.random() * (i + 1));
[array[i], array[randomIndex]] = [array[randomIndex], array[i]];
}
return array;
}
i
を配列の長さから 1 ずつ減らしながらループします。
ES6の Array.prototype.slice()と Math.random()を使う方法
この方法は、ES6以降で使用できる新しい方法です。
function shuffle(array) {
return array.slice().sort(() => Math.random() - 0.5);
}
array
のコピーを作成します。
比較
それぞれの方法の性能と利点・欠点は以下の表の通りです。
方法 | 性能 | 利点 | 欠点 |
---|---|---|---|
Fisher-Yatesシャッフルアルゴリズム | 中程度 | シンプルでわかりやすい | 古いブラウザではサポートされていない可能性がある |
forループとMath.random()を使う方法 | 低い | シンプル | 非効率的 |
ES6のArray.prototype.slice() とMath.random() を使う方法 | 中程度 | ES6以降で使用できる | 配列のコピーを作成する必要がある |
どの方法を使用するかは、要件と使用する JavaScript のバージョンによって異なります。
シンプルなソリューションが必要で、古いブラウザとの互換性が重要でない場合は、forループ
とMath.random()
を使用する方法が適しています。
パフォーマンスが重要で、ES6以降を使用できる場合は、Fisher-YatesシャッフルアルゴリズムまたはArray.prototype.slice()
とMath.random()
を使用する方法が適しています。
javascript