シャッフルのアルゴリズム Fisher-Yates shuffle

配列をランダムに並べ替える（シャッフルする）とき、基本的には各言語でライブラリがすでに用意されていると思います。もちろんそれを使うことになんの問題もないのですが、LeetCode を解いているとたまにシャッフル関数を自作させる問題が出てきます。

ライブラリ関数を呼び出してその問題を終えるのは味気ないので、シャッフルさせるアルゴリズムを探してみたところ、Fisher-Yates shuffle と呼ばれるアルゴリズムがスタンダードなようです。

※正確にはそのアルゴリズムをプログラミング用に若干修正を入れたものらしいのですが、ここでは気にせずに使います。

ここではそのアルゴリズムを解説します。

Fisher-Yates shuffle の仕組み

単純です。

1. for文で n-1 番目の要素まですべての要素を順に見ていく
2. 現在の index 以降からランダムな index を選び、現在の index の要素と交換する

Go 言語で実装するならこんな感じです。

import (
  "math/rand"
)

func impl() {
  arr := []int{1,2,3,4,5}
  for i := 0; i < len(arr) - 1; i++ {
    r := rand.Intn(len(arr) - i) + i
    arr[i], arr[r] = arr[r], arr[i]
  }
  return arr
}

len(arr - 1) は 4 なので、4 回ほどループが繰り返されます。index でいうと 3 までです。 len(arr) でも別にいいのですが、4 番目の index 以降の index は 4 しかないので、同じ場所を交換するというムダな操作が走ります。

rand.Intn(num int) は 0 ~ num-1の数字をランダムに返します。num は含まれないのが注意です。最大でも rand.Intn(5) という式しか現れないので、i ~ 4 まででランダムな数字を返し続けます。なおシードを設定したほうが良いです。

おわりに

単純だったので覚えておきたい。