Permutations, a simple Algorithm
This post provide a simple method to calculate all the pemutations and it is, at the same time, a tribute to @antirez, the Redis creator, one of the greatest IT people that the world knows.
If you think the permutation algorithm is tricky to develop without a reference, the following is the trivial solution I found, if you read it one time you’ll never forget it.
Let’s assume you want the permutations of the following list:
a b c d
Consider the list formed by just the first element:
What are the permutations of ‘a’, of course they are just:
Ok, now, take the next element, b. The permutations of a and b are the permutations of a modified to include b in every possible position, that is before a, and after a:
(b) a a (b)
Take the next element. c. Insert c in very position of every permutation of ‘a b’:
(c) b a b (c) a b a (c)
and, with the other permutation of ‘a b’
(c) a b a (c) b a b (c)
and you get all the six permutations of ‘a b c’, and so on.
That is simple! :)