A Sort of Permutation

Practical lessons in the impractical permutation sort

factorial 0 = 1
factorial n = n * factorial (n - 1)
factorial n = if n == 0 then 1 else n * factorial (n - 1)

Although correct, it hurts me, for I don’t like to crack an egg with a sledgehammer, no matter how effective the sledgehammer is for doing so.

factorial n = product [1..n]

Software development should not be a trade of constructing difficulty from simplicity. Quite the contrary.

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)]

Possible solutions are generated systematically and evaluated until a suitable solution is found. […] The greatest weakness of generate-and-test procedures is combinatorial explosion.

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)
void permutation_sort(auto begin, auto end)
{
while (next_permutation(begin, end))
;
}

performance

the degree to which a system or component accomplishes its designated functions within given constraints, such as speed, accuracy, or memory usage

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Kevlin Henney

Kevlin Henney

2.9K Followers

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