Source file `batInnerShuffle.ml`

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
let array_shuffle ?state a =
  let random_int state n = match state with
    | None -> Random.int n
    | Some s -> Random.State.int s n in
  for n = Array.length a - 1 downto 1 do
    let k = random_int state (n + 1) in
    if k <> n then begin
      let buf = Array.unsafe_get a n in
      Array.unsafe_set a n (Array.unsafe_get a k);
      Array.unsafe_set a k buf
    end
  done

(*$Q
  Q.(array_of_size Gen.(2--15) small_int) (fun a -> \
    let a' = Array.copy a in \
    array_shuffle a'; \
    (Array.to_list a' |> List.sort BatInt.compare) = \
     (Array.to_list a |> List.sort BatInt.compare))
*)

(*$R
  let rec fact = function 0 -> 1 | n -> n * fact (n - 1) in
  let length = 5 in
  let test = Array.init length (fun i -> i) in (* all elements must be distinct *)
  let permut_number = fact length in
  let histogram = Hashtbl.create permut_number in
  for i = 1 to 50_000 do
    let a = Array.copy test in
    array_shuffle a;
    Hashtbl.replace histogram a ();
  done;
  assert_bool "all permutations occur" (Hashtbl.length histogram = permut_number)
*)