Compute a random permutation

Problem statement

Write a function to generate a uniformly random permutation of {0 ... n - 1} sequence and return its subset of the specified size k. By the way, you are given a random number generator that returns integers in the set {0 ... n - 1} with equal probability, try to use as few calls to the generator as possible.

EXAMPLE:

  Input: n = 19, k = 5

  Output: [14, 7, 13, 6, 9]

Solution

Here is the actual code of the algorithm that implements a solution to generate a uniformly random permutation in the given range and return its subset of the specified size:

func random(n: Int, k: Int) -> [Int] {
    // Prepare state of the algorithm
    var seq = (0...n - 1).sorted(), perm = [Int](repeating: 0, count: k)
    // Select at most k elements to output
    for lhs in 0..<k {
        // Pick the next exchange using random generator
        let x = Int.random(in: lhs...n - 1)
        // Exchange elements
        swap(&seq, lhs, x)
        // Copy result of the exchange into the output
        perm[lhs] = seq[lhs]
    }
    // Here is the answer
    return perm
}

Following is the traditional section with assertions to validate the code performs as advertised and establish a baseline for any improvement work in the future:

Generate a random permutation test assertions

Bits & pieces

This coding challenge features a very useful technique to unformly pick random elements from a sequence.

Lets get started!

The first statement prepares state of the algorithm by initializing two sequences seq and perm, such that variable seq represents sequence of numbers from 0 to n - 1 and variable perm represents subset of chosen elements by the algorithm:

// Prepare state of the algorithm
var seq = (0...n - 1).sorted(), perm = [Int](repeating: 0, count: k)

Here is the initial state of the algorithm after both sequences are ready for further transformations:

Initial state of the variables

The following snippet is the main loop to perform selection of the elements from the sequence of numbers in seq variable:

// Select at most k elements to output
for lhs in 0..<k {
    ... inner block of code ...
}

Every iteration of the loop processes yet another number in the original sequence using current position in lhs variable to adjust random number generator’s range:

Loop iteration to generate random permutation

This statement, the first in the loop uses a technique of self-adjusting range to exclude elements selected previously and retain the equal probability when selecting the next element from sequence using random number generator:

// Pick the next exchange using random generator
let x = Int.random(in: lhs...n - 1)

As you may have noticed every iteration randomly picks position of the next element from the original sequence into x variable:

Select next random element from the original sequence

Next statement performs an actual exchange between current element in position lhs and randomly chosen element in position x:

// Exchange elements
swap(&seq, lhs, x)

To keep the distribution of elements in the output sequence uniform, the code swaps elements in the current position (lhs variable) and the next one randomly selected (x variable):

Swap elements to keep distribution uniform

The last statement in the loop simply copies the result of the previous exchange into the output sequence perm:

// Copy result of the exchange into the output
perm[lhs] = seq[lhs]

Lastly, the element randomly selected is copied to the output sequence as is without any modifications:

Copy selected element to the output sequence

As soon as the main loop is over, perm variable should have a subset of uniformly random permutation in 0...n - 1 range of the specified size:

// Here is the answer
return perm

Finally, here is how the algorithm’s resulting state looks like, when the function is about to return results to the calling code:

Final state of the algorithm's internals

That’s all folks! 💾

Here is a Swift playground for this article at Github: Compute a random permutation.