The Q# standard library is equipped with an extensive collection of array functions, meeting a wide array of algorithmic requirements. It further includes a variety of functions, types, and operations beneficial for generating random values and handling different probability distributions.

However, a somewhat notable omission is the lack of a built-in feature for shuffling or randomizing an existing array. In this blog post, we will build a straightforward helper operation to bridge this functional gap.

Fisher-Yates shuffle 🔗

The algorithm we are going to introduce is a variation of the Fisher-Yates shuffle, often referred to as the Knuth shuffle. This method is known for its effectiveness in randomizing the order of elements within an array.

To begin, we initiate a generic blank operation named Shuffled. This operation takes any array ‘T[] that needs to be shuffled as its input and returns a randomized version of that array as its output. It’s important to classify it as an operation, rather than a function, because it involves generating random integers, and in Q#, these are designated as operations.

operation Shuffled<'T>(array : 'T[]) : 'T[] {
    // to do
}

The algorithm begins with an array of elements, generically typed as T[]’. We need to check if that array has at least the length of 2 - otherwise, there is really nothing to shuffle. We then generate a mutable duplicate of this array, named shuffled.

operation Shuffled<'T>(array : 'T[]) : 'T[] {
    let arrayLength = Length(array);
    if arrayLength <= 1 {
        return array;
    }

    mutable shuffled = array;
    // to do
    return shuffled;
}

Next, the algorithm sequentially progresses through the array, stopping just before the final element (thus, arrayLength - 2 in the loop).

operation Shuffled<'T>(array : 'T[]) : 'T[] {
    let arrayLength = Length(array);
    if arrayLength <= 1 {
        return array;
    }

    mutable shuffled = array;
    for i in 0..arrayLength - 2 {
        // to do
    }

    return shuffled;
}

During each iteration, indexed as i, a random index j is chosen, where j lies between the current index i and the array’s last index arrayLength - 1. The elements at indices i and j are then interchanged, using the built in Swapped function.

operation Shuffled<'T>(array : 'T[]) : 'T[] {
    let arrayLength = Length(array);
    if arrayLength <= 1 {
        return array;
    }

    mutable shuffled = array;
    for i in 0..arrayLength - 2 {
        let j = DrawRandomInt(i, arrayLength - 1);
        set shuffled = Swapped(i, j, shuffled);
    }

    return shuffled;
}

Upon the loop’s completion, the algorithm yields the array, now shuffled - which is returned as the output of the operation.

The essence of this algorithm’s efficiency and accuracy lies in its ability to guarantee that each element possesses an equal chance of being placed in any position within the array. This uniform probability distribution is achieved by examining each spot in the array and swapping it with a position chosen randomly from those not yet finalized.

Trying it out 🔗

We can test our custom operation now, by observing how it would randomize an ordered array. Here is a simple Q# program that could test that.

let array = MappedOverRange(i -> i, 0..10);
Message($"Ordered array: {array}");

let shuffled = Shuffled(array);
Message($"Shuffled array: {shuffled}");

We start with an ordered array of 11 elements - 0 to 10, which we can create using MappedOverRange array function. We then print it out, so that we can get visual confirmation of the fact that it is indeed sorted. We then call our new Shuffled operation, and print its result, which at this point should be a randomized copy of the original array.

Here is the sample output:

Ordered array: [0,1,2,3,4,5,6,7,8,9,10]

Shuffled array: [5,9,3,10,4,6,8,2,0,7,1]

Practical example 🔗

Let’s close off with a more practical example. Suppose that you would like to create a random boolean array, but with the constraint that it is balanced - that is, it has the exact same of true elements as it has false elements. This is a requirement I faced recently, hence I wanted to bring this up here.

We could achieve this manually, by using the following formula:

1. Initialize two counters for the number of true and false values.
2. Randomly draw a bit.
3. Check the counters to ensure neither has reached its limit, which would be equal to half the size of the array.
4. Once the limit is reached for true, only add false values, and vice versa. Continue until the array is filled with the required number of elements.

This has the following Q# representation:

operation BalancedBoolArrayV1(size: Int) : Bool[] {
    mutable trueCount = 0;
    mutable falseCount = 0;
    mutable resultArray = [];

    Fact(size % 2 == 0, "Size must be divisible by 2");
    let halfSize = size / 2;
    
    for i in 0..size - 1 {
        if trueCount < halfSize and falseCount < halfSize {
            let randomBit = DrawRandomBool(0.5);
            if randomBit {
                set trueCount += 1;
            } else {
                set falseCount += 1;
            }
            set resultArray += [randomBit];
        } elif trueCount >= halfSize {
            set resultArray += [false];
        }
        else {
            set resultArray += [true];
        }
    }
    
    return resultArray;
}

We can test this with the following program:

let balancedBoolArray1 = BalancedBoolArrayV1(8);
Message($"Balanced bool array V1: {balancedBoolArray1}");

And indeed, the output should be a random balanced bool array, something like:

Balanced bool array V1: [True,False,True,True,True,False,False,False]

Yet, with the new Shuffle at our disposal, we can skip the manual process and efficiently and simply generate a balanced array using that operation instead. For most use cases, this is likely the preferable option, primarily due to its efficiency and straightforwardness. The code is much cleaner as well.

First, we initiate an array filled solely with true elements, which is half the size of the intended array. This array is then padded with an equal number of false elements, utilizing the Q# Padded function. Consequently, we end up with an array where the first half comprises exclusively false elements, and the latter half contains only true elements. Finally, we shuffle the array using our new Shuffle operation.

operation BalancedBoolArrayV2(size: Int) : Bool[] {
    Fact(size % 2 == 0, "Size must be divisible by 2");
    
    let array = [true, size = size/2];
    return Shuffled(Padded(-size, false, array));
}

We can test it in a similar fashion as before:

let balancedBoolArray2 = BalancedBoolArrayV2(8);
Message($"Balanced bool array V2: {balancedBoolArray2}");

And the output should be a balanced random bool array, resembling this:

Balanced bool array V2: [False,True,False,True,False,True,True,False]

And that’s it! Happy coding - and if you are interested in the source code for this article, it is available on Github.