# Compute a random permutation

17 Sep 2018### 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:

### 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`

variableThe 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.