More natural/preferred way to shuffle an array

Hi,

Please let me know if there is another place where I should be asking this.

I want to generate a “shuffled” list or array from let’s say [|1;2;3;4;5|]. I wrote the following code, which works; however, I would like to know if there is a more natural way to do this with OCAML. Please don’t mind the variable names.

    (* pops a random index, and returns the (value, thelist) *)
    let pop_random_value aList =
      let n  = List.length aList in
      let i = Random.int n in
      let value = List.nth aList i in
      (value, filter_value aList value)
    
    let prepend_value aList aVal = aVal::aList
    
    let get_random_array size  =
      let n = Array.init size (fun v -> v+1)  in
      let ni = ref (Array.to_list (Array.init size (fun v -> v))) in
      let returnlist = ref [] in
      while ((List.length !ni) <> 0) do
        let (value, newlist) = pop_random_value !ni in
        ni := newlist;
        returnlist := prepend_value !returnlist n.(value)
      done;
      !returnlist

Quite often uses of List.nth tend to indicate that the 'a list data structure is not very adapted to the problem at hand.

In your case, what you are trying to achieve is generally called a random permutation , also known as a shuffle. A good algorithm for implementing such shuffle is the Knuth shuffle algorithm which can be written as

 let knuth_shuffle a =
  let n = Array.length a in
  let a = Array.copy a in
  for i = n - 1 downto 1 do
    let k = Random.int (i+1) in
    let x = a.(k) in
    a.(k) <- a.(i);
    a.(i) <- x
  done;
  a

To explain briefly Knuth algorithm, at each step i, it divides the array a in two part: the shuffled part at indices
k>i and the not yet shuffler part for i≤k. Then at each step, a new value is picked randomly from the not-yet shuffled part and placed at the position i which increases the size of the shuffled part by one. In other words, the Knuth algorithm is a method to implement in-place the separation between the not-yet sampled and already sampled lists that you implemented in get_random_array.

An important point is that the complexity of Knuth shuffle belongs to the O(n) class, whereas your function complexity scales as O(n²).

7 Likes

Great! Thank you so much!

Thank you for pointing out the complexity issue as well.

I was trying to be more functional, but in certain cases, I realize, it’s better to think with for loop and mutations (although you copied it first in your algorithm which is great) etc.

I’m not privileged enough yet to do it myself :slight_smile: but I think it would be useful to retitle this thread “More natural/preferred way to shuffle an array (in OCAML)”

2 Likes

Thanks for the suggestion. I have changed the title of the Post. I hope the OP doesn’t mind.

2 Likes

Here is a somehow more functional way of shuffling a list. It is not as efficient in practice as Knuth shuffle algorithm, the expected time complexity is only O(n log n). But it also makes clear that it uses O(n log n) random bits (expected again), and that is the information-theory lower bound. I like the fact that it mirrors the quicksort algorithm.

let rec shuffle = function
  | [] -> []
  | [single] -> [single]
  | list -> 
    let (before, after) = List.partition (fun elt -> Random.bool ()) list in 
    List.rev_append (shuffle before) (shuffle after)
5 Likes