Create a collection of binaries with random set positions

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

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

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
`