One of my more popular articles from 2010 was my post on how to produce the Cartesian product of arbitrarily many sequences of the same type. That is, we have some sequences, say {10, 20, 30} and {200, 300, 400}, and we wish to produce the sequence of all possible combinations:
{
{10, 200}, {10, 300}, {10, 400},
{20, 200}, {20, 300}, {20, 400},
{30, 200}, {30, 300}, {30, 400}
}
A related question that I did not answer was “how do you produce all possible permutations of a sequence?” That’s the question we’re going to explore for the next few episodes.
First off, we should define “permutation”. A permutation for our purposes is a possible re-ordering of a finite sequence of unique elements. I’m not going to deal with more complex permutations like finding all the orderings of a sequence containing three blue socks, a red sock and a green sock; we’re going to assume that all the socks are unique. In fact, let’s just assume that the sequence we’re permuting is the n-item sequence {0, 1, 2, 3, .. n - 1}. As we’ll see, if we can permute that sequence, we can permute any sequence of n unique items.
How many permutations of size n are there? We could try enumerating them and look for a pattern. Clearly there is only one permutation of the sequence {0}; there is no way to re-order it. There are two permutations of the two-item sequence: {0, 1} and {1, 0}.
What about the three item sequence? {0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}. Six.
What about the four item sequence? {0, 1, 2, 3}, {0, 1, 3, 2}, … uh, this is going to get long.
Let’s work it out mathematically instead of enumerating them.
For an n-item sequence, there are n different ways to choose the first element. That first element is then unavailable for the second element, so there are n-1 ways to choose the second element, n-2 ways to choose the third, and so on down to n-(n-1) = 1 way to choose the last element; it has been entirely determined by the previous choices. Multiply all those together and you get n! — which matches our results so far, since 1! = 1, 2! = 2, 3! = 6.
Wait, we forgot a sequence: what are all the permutations of the empty sequence, with zero elements, { }? Obviously there is only one permutation of the empty sequence, which is the empty sequence. And by convention, 0! is said to be 1, so we’re good. We have shown that there are n! permutations of an n-item sequence.
OK, so how are we going to enumerate all the permutations? There are a number of ways to do so; the way I’m going to show you uses recursion. As we’ve discussed many times before, every recursive algorithm has the same structure:
- If we are in a trivial case then solve the trivial problem and return.
- Otherwise, we are in a complex case.
- Reduce the complex case to a finite number of simpler problems.
- Solve the simpler problems recursively.
- Combine their solutions to solve the complex problem and return.
We have a trivial case: we know that the only permutation of the zero-element sequence is itself.
Now suppose we have in hand a sequence of all the permutations of size three, and we want all the permutations of size four. That is, we have:
{
{0, 1, 2},
{0, 2, 1},
{1, 0, 2},
{1, 2, 0},
{2, 0, 1},
{2, 1, 0}
}
How can we use this to produce the sequences of size 4? Well, there are 6 permutations in this sequence. We know that we’re going to need to come up with 24 somehow. This gives us the intuition that each one of those 6 should be able to generate 4 more sequences. And in fact it can: we modify each sequence by inserting the 3 before the first element, before the second element, before the third element, or after the third element:
{
{3, 0, 1, 2},
{0, 3, 1, 2},
{0, 1, 3, 2},
{0, 1, 2, 3}, OK that took care of { 0, 1, 2 }, let's move on
{3, 0, 2, 1},
{0, 3, 2, 1},
{0, 2, 3, 1},
{0, 2, 1, 3}, OK that took care of { 0, 2, 1 }, let's move on
{3, 1, 0, 2},
...
}
And sure enough, we enumerate all the permutations this way, without any duplication. We have the makings for a classic recursive algorithm here: we have a base case, and we have a way to use the solution to a smaller problem in order to produce the solution to a larger problem.
Already this is enough to write correct code, but we won’t quite yet. Next time on FAIC I’m going to discuss a small change we can make to the sketched-out algorithm that adds a small amount of complication in exchange for a rather elegant property.
Fabulous adventures in coding 
Great post Eric! As always..
Well I approached it slightly differently… instead of taking one element and inserting it at each possible index in each permutation, I took each element and prepended it to the front of each permutation. I could post my implementation here, but I think I want to see yours first 🙂
Great timing ,Eric! Currently at my workplace we have just changed our interview tests and introduced this exact problem among others. I’ll sure follow along this series 😉
Good luck with double digit sets, at Length=13 your looking at 6,227,020,800 permutations, a bit more than a 32 bit index can store.
Sorry, couldn’t resist :p
I didn’t say I was going to index them, just enumerate them. Though enumerating all of those six billion combinations might take a while.
I might get to indexing them in a later episode, we’ll see.
About one (or two, don’t remember) year ago I had to write a method to produce permutations for a software, but it didn’t actually produce all the permutations like this, instead I wrote a function to get the nth permution of a sequence, and was not a recursive function.
Here’s my “prepend to front” solution. I can’t think of an elegant “all insertions” implementation.
static IEnumerable<IEnumerable> Perms(IEnumerable xs) {
if (!xs.Any())
yield return xs;
else
foreach (var x in xs)
foreach (var p in Perms(xs.Where(y => !y.Equals(x))))
yield return new [] { x }.Concat(p);
}
Hmm, the editor removed my type parameters, but you get the gist.
This will have pretty darn poor performance. Note that you’re enumerating the source enumerable multiple times. Once for `Any` and (if it has items, which it very often will) again in the outer `foreach`, and then again in what you pass to the recursive call. What’s worse, since the method is recursive each of these enumerations aren’t going to be simple lists that are being iterated for a very small cost, you’re performing queries that are filtering items again and again and again.
Hi, a few points in response.
– I was going for a concise solution, not a fast one.
– Any() should be O(1); it doesn’t need to traverse the entire sequence.
– Even so, because these are enumerables, data will only be generated on demand. I can take the nth item from this sequence without having to compute the preceding items. That might be a big win, depending on your application.
– Trading enumerables for lists only grants you a constant factor improvement. You still have to perform exactly the same abstract operations with the same complexity. To do better, you’d need to use a more complex data structure, preferably with O(1) removal and concatenation, which in turn would bring its own large constant factors.
– What’s wrong with recursion? No work is duplicated here since Perms() is never called twice with the same value.
In the deepest calls, I’m pretty sure xs.Any() will have to walk the entire input sequence, because it can only figure out that there is no element by trying to get the first one, and if all elements are filtered in the calls above this will consume the entire input.
I’m not sure how to avoid this here, but one trivial improvement would be to replace “yield return xs” with “yield return new T[0]” – otherwise you are building your permutations on top of a very expensive empty sequence.
Not really, the “Where” enumerator will stop after finding the first element, all of them are absed on the “yield” operator wich is lazy.
But yes, some operations will be done a few more times than necessary.
‘Not really, the “Where” enumerator will stop after finding the first element’
Uh, no. You’re doing Where(y => !y.Equals(x)).Any(), which will stop after finding the first element for which !y.Equals(x) … so this is O(n).
Do you know factoradic?
http://en.wikipedia.org/wiki/Factorial_number_system
I might get to that in a later part of this series.
Here is my recursive implementation of Permutations:
public static IEnumerable Permutations( this T[] array ) { if ( array == null ) throw new ArgumentNullException( "array" ); if ( array.Length <= 1 ) yield return array; else for ( int i = 0; i eI.Concat( aT ) ) ) yield return result; } }RemoveAt and Concat are self-explanatory helper methods.
Pingback: Hill Climbing Variations | Little Algorithms
Pingback: Producing combinations, part one | Fabulous adventures in coding
Pingback: Basic playing card generation and shuffle | DL-UAT
Pingback: algorithm - ¿Cuál es la mejor manera de encontrar todas las combinaciones de elementos en un array?