Test shuffling for Sequence.shuffle_buffer

shuffle.ml

open Sequence.Infix

let px = 1000
let l = px/5
let buf_l = l/2
let s = 0 -- (l-1)

let m = Array.make_matrix l l 0

let fill_array =
  Sequence.iteri @@ fun i j -> m.(i).(j) <- m.(i).(j) + 1

let color samples c =
  let exp = float samples /. float l in
  let x = truncate @@ (exp -. float c) /. exp *. 150. in
  if x > 0 then
    Graphics.rgb (50+x) 50 50
  else
    Graphics.rgb 50 (-x+50) 50

let show samples px m =
  let l = Array.length m - 1 in
  let ratio = px / l in
  for i = 0 to l do
    for j = 0 to l do
      Graphics.set_color @@ color samples m.(i).(j) ;
      Graphics.fill_rect (i*ratio) (j*ratio) ratio ratio ;
    done
  done

let () =
  Random.self_init () ;
  Graphics.open_graph "" ;
  Graphics.(set_color @@ rgb 0 0 0) ;
  Graphics.resize_window px px;
  Graphics.auto_synchronize false;
  let samples = ref 0 in
  while true do
    incr samples ;
    fill_array @@ Sequence.shuffle_buffer buf_l s ;
    if !samples mod 1000 = 0 then begin
      Graphics.set_window_title @@ Printf.sprintf "Samples: %i" !samples ;
      show !samples px m ;
      Graphics.synchronize () ;
    end
  done

(*
Local Variables:
compile-command: "ocamlfind ocamlopt -package sequence,graphics -linkpkg shuffle.ml -o shuffle"
End:
*)

Sequence.shuffle_buffer is designed to be able to shuffle infinite (or just very big) lazy streams while consuming a limited amount of memory. It's not perfect shuffle at all.

In the following picture, origin bottom left. x is shuffled position, y is original position. deviation from gray is bias. As you can see, no elements at the end can end up in the beginning.

Here is the picture for Fisher–Yates shuffle