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

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