Create a collection of binaries with random set positions

Question

I would like to create a collection of binaries with n set bits and total length should be between n and 31; also those set bits should be randomly positioned. For example if n = 3, then [1;0;1;0;1], [1;0;0;1;1;] and [1;1;1;0;0] should all be possible with equal chance. Below is my implementation and any feedback is welcome.

/// <summary>
/// Create a random collection of binaries, between n and 31 elements, with n bits are set. 
/// The set positions should be random too.
/// </summary>
/// <param name="n">The number of set bits in the collection; must be positive and less than 32</param>
let createRandomBinary (n : int) = 
 if n > 31 || n < 0 then ArgumentException("invalid input: must be positive and less than 32", "n") |> raise
 let ran = new Random()
 let mutable totalLength = ran.Next(n, 32) // [n, 32)
 match totalLength with
 | x when x = n -> Array.init n (fun _-> 1) // all bits are set case
 | _ -> let res : int array = Array.zeroCreate totalLength // initialise a result with all 0s.
 let indices = ResizeArray(seq{0..totalLength - 1}) 
 let mutable counter = n
 let rec shuffle = function
 | 0 -> res // all n 1s have been set randomly so return the result
 | _ -> counter <- counter - 1
 let i = ran.Next(0, totalLength) // randomly pick an index and set to 1
 res.[indices.[i]] <- 1
 indices.RemoveAt(i) // remove the chosen index so it won't be set twice
 totalLength <- totalLength - 1 // decrease the length for next random index pick
 shuffle counter
 shuffle counter

• Maslow: I'd consider making it pure by way of moving the random up to being a parameter then you can seed it for testing.

Answer 1

The logic to generate a length between n and 31 has nothing to do with creating a random list of a given length with a given number of set bits. Split them out into multiple functions.

This highlights the usefulness of making the randomness a parameter of the function, so do that too.

Use better names than n and x.

invalidArg is prettier.

Your matchtotalLength` is unneeded; the second path always works and the first isn't common enough to be worthwhile.

A for loop is a much better expression of intent when mutating res, and you can drop a lot of silliness by doing so.

By now we have

let generateBits (rand : Random) (length : int) (set_bits : int) =
 if not (0 <= set_bits && set_bits <= length) then
 invalidArg "set_bits" "must be nonnegative and no biger than length"
 let res = Array.zeroCreate length
 let indices = ResizeArray(seq{0..length - 1})
 for i in 0 .. set_bits - 1 do
 let random_index = rand.Next(0, length - i)
 res.[indices.[random_index]] <- 1
 indices.RemoveAt(random_index)
 res
let createRandomBinary (rand : Random) (max_length : int) (set_bits : int) =
 generateBits rand (rand.Next(set_bits, max_length)) set_bits

and your old function is equivalent to createRandomBinary (Random()) 32.

indices.RemoveAt is slow. Luckily we don't have to do it; we can get a random sample by using an array and just swapping the used elements to the end:

let indices = Array.init length id
for i in 0 .. set_bits - 1 do
 let random_index = rand.Next(0, length - i)
 res.[indices.[random_index]] <- 1
 let item = indices.[random_index]
 indices.[random_index] <- indices.[length - i - 1]
 indices.[length - i - 1] <- random_index
res

Then note that instead you can just set any bits of the array and shuffle it after:

let shuffle (rand : Random) (array : int []) =
 Array.iteri (fun i elem ->
 let index = rand.Next(i, Array.length array)
 array.[i] <- array.[index]
 array.[index] <- elem
 ) array
let generateBits (rand : Random) (length : int) (set_bits : int) =
 if not (0 <= set_bits && set_bits <= length) then
 invalidArg "set_bits" "must be nonnegative and no biger than length"
 let res = Array.init length (fun i -> Convert.ToInt32 (i < set_bits))
 shuffle rand res
 res
let createRandomBinary (rand : Random) (max_length : int) (set_bits : int) =
 generateBits rand (rand.Next(set_bits, max_length)) set_bits