# 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]
}
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: ### 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: 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: 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: 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): 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: 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: That’s all folks! 💾

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