RYO.dev

最終更新日:

ダステンフェルドのアルゴリズムを使ったランダムシャッフル

  1. ランダムシャッフルに使うアルゴリズム
  2. ダステンフェルドのアルゴリズム
  3. フィードバック

ランダムシャッフルに使うアルゴリズム

「javascript ランダムシャッフル」とググって出てきた記事ではたいてい、フィッシャー–イェーツのシャッフル (Fisher–Yates shuffle)アルゴリズムを使ってランダムシャッフルを実現しています。

Wikipediaでは、このアルゴリズムを言語化して紹介しています。

  1. 1 から N までの数字を書く。
  2. まだ消されてない数字の数を数え、1 からその数以下までのランダムな数字 k を選ぶ。
  3. 残っている数字から k 番目の数字を消し、別の場所にその数字を書き出す。
  4. すべての数字が消されるまで手順 2, 3 を繰り返す。
  5. 手順3で書かれた数列が元の数値からのランダム順列となる。

これと、Wikipediaの例をもとに、配列の要素をランダムシャッフルするコードを書いてみるとこうなります。

const a = ["a", "b", "c", "d"];
const N = a.length;

for(let i = N; i > 0; i--) {
  const k = Math.floor(Math.random() * i);
  a.push(a.splice(k, 1).toString());
}

a.splice(k, 1)は、a[k]の位置から1つの要素を取り除きます。splice()メソッドは、取り除かれた要素を含む配列を返します。それを、toString()メソッドで文字列に変換します。push()メソッドを使ってその文字列を配列aの末尾に追加します。

...どうですか?
あなたが見た記事で紹介されているコードと一緒ですか?

違うはずです。

しかし、これがフィッシャーとイェーツのアルゴリズムです。

あなたがよく目にするコードはダステンフェルドのアルゴリズムです。これは、コンピュータでの使用を想定してフィッシャーとイェーツのアルゴリズムを改良したものです。

次のセクションでダステンフェルドのアルゴリズムについて触れていきます。

ダステンフェルドのアルゴリズム

Wikipediaではこのアルゴリズムについて次のように説明しています。

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

では、これをコードで表現してみましょう。次のようになります。

const a = ["a", "b", "c", "d"];
const n = a.length;

for(let i = n - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [a[i], a[j]] = [a[j], a[i]];
}

a[j] と a[i]を交換する」コードは以下のコードで実現しています。

[a[i], a[j]] = [a[j], a[i]];

これは分割代入という手法です。

フィードバック

ご意見やお聞きしたいことがございましたら、TwitterのDMメールにご連絡ください。