1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I'd consider making it pure by way of moving the random up to being a parameter then you can seed it for testing. \$\endgroup\$ – Maslow Feb 3 '16 at 13:46
2
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.