配列を効率よくシャッフルする【フィッシャー–イェーツ】

はじめに

ゲームや単語帳など一定の要素をシャッフルする処理を書く必要が発生することはプログラミングをしているうえでよくあることだと思います。様々な手法を使ってシャッフルが行われていますが、実はすでに効率よくシャッフルするためのアルゴリズムが存在しています。

今回はそのアルゴリズムである「フィッシャー–イェーツのシャッフル」を用いた実装をご紹介します。

実装例

今回はJavaScriptとPythonでの実装例をご紹介します。

JavaScript実装例

const array = [1, 2, 3, 4, 5];

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

Python実装例

import random

array = [1, 2, 3, 4, 5]
for i in range(len(array) - 1, 0, -1):
    j = random.randint(0, i)
    array[i], array[j] = array[j], array[i]

仕組み

配列の末尾から順番に乱数で求めたインデックスの要素とデータを交換します。交換した末尾側の要素はシャッフル済みとして処理されますのでそれ以降はデータ交換の対象とはなりません。

シャッフル未確定の配列末尾と乱数で求めたインデックスの要素を交換することでシャッフルします。入れ替えられた配列末尾のデータは、配列長 – 1 のループ回数ため非常に効率よくシャッフルを行うことができます。

視覚的にわかりやすくするために過程を表示するプログラムを作成しました。

赤枠が交換される要素、水色がシャッフルが確定した要素です。「シャッフル」ボタンを押すと何度でもシャッフルが可能ですので是非試してみてください。