knuth/fisher/yates shuffle backwards

[shwestrick]

This code for sequential knuth/fisher/yates shuffle is incorrect; the random swap index is chosen in the range [0,i] for current increasing position i. We can keep increasing i, but then the random chosen swap index should be in the range [i,n-1].

mpllib/lib/github.com/mpllang/mpllib/Shuffle.sml

Lines 10 to 28 in b0a478b

	(* inplace Knuth shuffle [l, r) *)
	fun inplace_seq_shuffle s l r seed =
	let
	fun item i = AS.sub (s, i)
	fun set (i, v) = AS.update (s, i, v)
	(* get a random idx in [l, i] *)
	fun rand_idx i = Int.mod (Util.hash (seed + i), i - l + 1) + l
	fun swap (i,j) =
	let
	val tmp = item i
	in
	set(i, item j); set(j, tmp)
	end
	fun shuffle_helper li =
	if r - li < 2 then ()
	else (swap (li, rand_idx li); shuffle_helper (li + 1))
	in
	shuffle_helper l
	end