# A Sort of Permutation

## Factorial redux

In case your only recollection of factorial is as a rather uncompelling demonstration of recursion, what you need to know is that the numbers get very large very fast.

`factorial 0 = 1factorial n = n * factorial (n - 1)`
`factorial n = if n == 0 then 1 else n * factorial (n - 1)`
`factorial n = product [1..n]`

## Searching permutation space

Python’s permutations function returns an iterable that can be used to iterate through successive rearrangements of the values given as its input:

`list(permutations([1, 2, 3]))`
`[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]`
`list(permutations([1, 2, 3, 4]))`
`[(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2), (2, 1, 3, 4), (2, 1, 4, 3), (2, 3, 1, 4), (2, 3, 4, 1), (2, 4, 1, 3), (2, 4, 3, 1), (3, 1, 2, 4), (3, 1, 4, 2), (3, 2, 1, 4), (3, 2, 4, 1), (3, 4, 1, 2), (3, 4, 2, 1), (4, 1, 2, 3), (4, 1, 3, 2), (4, 2, 1, 3), (4, 2, 3, 1), (4, 3, 1, 2), (4, 3, 2, 1)]`
`filter(is_sorted, permutations(values))`
`next(filter(is_sorted, permutations(values)))`
`def permutation_sort(values):    return list(next(filter(is_sorted, permutations(values))))`
`def permutation_sort(values):    return list(next(        each for each in permutations(values) if is_sorted(each)))`
`def is_sorted(values):    pairs = zip(values, islice(values, 1, None))    return all(i <= j for i, j in pairs)`

## Minimum viable permute

The Python out-of-place implementation of permutation sort is quite compact, but the in-place C++ version is even more minimal:

`void permutation_sort(auto begin, auto end){    while (next_permutation(begin, end))        ;}`

## Let’s talk performance

Apart from being eye-opening, instructive and fun — isn’t that enough? — of what use is permutation sort? One use is for having — even provoking — that awkward conversation about performance.

--

--

## More from Kevlin Henney

consultant · father · husband · itinerant · programmer · speaker · trainer · writer

## Get the Medium app

consultant · father · husband · itinerant · programmer · speaker · trainer · writer