fisher yates アルゴリズムで配列シャッフル
ローカルリポジトリを掃除していたらFisher-Yates法 の実装が見つかりました。
コミットのついでに紹介します。このアルゴリズムを使うと配列が O(n)時間 でシャッフル出来ます。
local fun swap xs i j = (* swap xs[i] xs[j] *) let val tmp = A.sub (xs, i) val _ = A.update (xs, i, A.sub(xs, j)) val _ = A.update (xs, j, tmp) in () end in fun random_shuffle xs : unit = let fun loop xs i = let val j = R.range (0,i) (R.newgen()) in swap xs i j end in for (A.length xs downto 1) (loop xs) end end
使ってみます。
fun main _ = let val xs = A.fromList ((R.rangelist (0,10) (10,R.newgen()))) in println (toString xs); println "randomize..."; F.random_shuffle xs; println (toString xs) end val _ = Main.main "";
実行結果
$ mlton random_array.mlb && ./random_array 1,1,10,9,1,3,9,2,3,7 randomize... 1,9,10,3,7,1,1,3,9,2
まぁ、配列を破壊的に変更するのでSMLに向いてないカンジがありますけど…。
破壊せずに効率的に書くテクニックとかあるんでしょうか。
例のごとくコード全体はcodeplexに置いてあります。