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に置いてあります。