Home > Software > Combinations and permutations

Combinations and permutations


Unfortunately, a lot of algorithms fall under the Murphy law that says “Any simple theory will be worded in the most complicated way”.
Writing software in such a way that every developer understands is a challenge, but sure pays of in the end. Explaining an algorithm in a simple way is essential. And not only the algorithm, but the idea itself. Because, as always, this is what really matters. If you get the idea then, not only that you can implement the algorithm, but you will be able to play with it in such way that you can adapt it and optimize it to more and more complex problems.
About the idea behind the generation of combinations and permutations I will talk today. The problem is to generate all (or a random one) the combinations/permutations of an array of size n.
In many sources, this starts saying that it is done recursively. In this case I would say that this is an implementation details. Let’s take a few steps back and look at the basic idea.

Combinations

I will start with combinations, as they are simpler. A combination is practically a subset of the initial set, because its elements are not ordered. So think of it this way: for every element we have to make a simple decision – is or is not in the combination.
So generating a random combination is the same as generating n booleans or a number represented on n bits, where the ith boolean/bit is true/1 if and only if the element i is in the combination. Generating a number of n bits can be complicated for a large n (in order of millions) so then we will stick to generating n booleans or n/w numbers of w digits where w is the size of a word in bits (16, 32, 64).
The same way enumerating all combinations means iterating through all the numbers from 0 (if we consider the empty set as a combination) or 1 to 2n-1. Every number will represent a combination as above.

Example
For n = 3, there are 7 combinations (excluding the empty set). For the sake of example let’s consider the original array being {a, b, c}
For combination number 3, the binary representation is 011. This means that the combination is {b, c}.

# Binary Combination
1 001 {c}
2 010 {b}
3 011 {b, c}
4 100 {a}
5 101 {a, c}
6 110 {a, b}
7 111 {a, b, c}

Permutations

Because the order of elements is important, generating permutation is slightly complicated. But again what is the idea? For every element (starting in order with the first) we have to make one decision: where to place him in the final permutation. For the first element we have n positions available, for the second n-1, and so on, until the last where only one position remained available. Imagine that we want to arrange n pupils in n desks. The first one can choose each of the n desks, the second one can choose from the remaining n-1 desks and the last pupil must sit into the last available seat.
We will encode a permutation as an array of n numbers, where the ith element represents the position of the ith element in the remaining positions. This being said, for generating a random permutation will have to generate n-1 random numbers, first from 0 to n-1, second from 0 to n-2 and so on (the last n number is considered to be 0). Or the equivalent will be to generate a random number between 0 and n! and represent it in a variable decreasing base. As n can be very large only calculating n! will be a bit of a problem, so we will stick to the first approach.
Enumerating all permutations is fairly easy in this light. Iterate through numbers from 0 to n!-1 and represent them in a variable base (or start with 0 and increase by 1 in variable base). This way you will have the permutation representation.
It is pretty easy to convert this representation to a different one, where the ith element represent the final index in the permutation of the ith element of the original array.

Example
For n = 3, there are 6 permutations. For the sake of example let’s consider the original array being {a, b, c}
For permutation number 3, the representation is 011. This means that the permutation is {b, c}.

# Representation Indexes Permutation
0 000 012 {a, b, c}
1 010 021 {a, c, b}
2 100 102 {b, a, c}
3 110 120 {c, a, b}
4 200 201 {b, c, a}
5 210 210 {c, b, a}

But what are permutations really good for? If you write a card game, dealing the cards is actually generating a permutation of 52 (or maybe less in some games) numbers. The card numbers and colors are ordered and have a number between 0 and 51 assigned.

It is obvious that the above methods can be implemented both in a recursive or non-recursive manner. Just for fun, I included here a Java implementation for a permutation generator, designed like an iterator.

From the articles I read so far, I always thought that combinations and permutations are explained in a misleading way with too much emphasis on the implementation, instead of focusing on the idea of the algorithm. This is what I tried to provide here. Hope you like it and find it useful.

Categories: Software Tags:
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: