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 i^th 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 2ⁿ-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 i^th element represents the position of the i^th 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 i^th element represent the final index in the permutation of the i^th 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.

Brain teaser: digits

I heard an interesting, even though easy, problem in the brain teaser category.
The digits of the numbers between 1 and 1999 are concatenated together in this order to create a new number. What is the 1999 digit of this number?
After you solve it, remember that this is for a 5th grade kid :D.

Overlapping rectangles

I come up to another geometry problem while coding.
Problem: Found the overlapping region of two rectangles with parallel sides (two by two).
Solution: Actually quite simple.

The problem can be reduced (from two dimensions to one dimension) to find the overlapping section of two segments on the same line. Let’s say that the first segment is from x1 to x2 (x1<=x2) and the second one is from z1 to z2 (z1v2 then the segments do not overlap.

By extension to rectangles specified by (top,left) and (bottom,right) corners, the overlapping region of two rectangles:

1. (x1,y1)(x2,y2), where x1 <= x2 and y1 <= y2
2. (z1,t1)(z2,t2), where z1 <= z2 and t1 <= t2

will be (v1=max(x1, z1), w1=max(y1,t1))(v2=min(x2, z2), w2=min(y2,t2)). If v1 > v2 or w1 > w2 then the two rectangles do not overlap.

To express it in plain English, we calculate the maximum of the lower coordinates and the minimum of the upper one. If the results maintain the same relationship, then there is no overlap.

Please see the image below to visually illustrate the above.

If interested I also have the SVG code for this image:

<svg width="640" height="480" xmlns="http://www.w3.org/2000/svg">
  <g>
    <title>Overlapping Rectangles</title>
    <text fill="#111111" stroke="#111111" stroke-width="3" x="187" y="52" id="text1" font-size="14" font-family="serif" text-anchor="middle" xml:space="preserve">Overlapping segments on the same line</text>
    <line id="l1" y2="78" x2="243" y1="78" x1="83" stroke-width="5" stroke="#00dd00"/>
    <line id="l1" y2="78" x2="283" y1="78" x1="103" stroke-width="5" stroke="#0000dd"/>
    <line id="l1_2" y2="78" x2="243" y1="78" x1="103" stroke-width="5" stroke="#dd0000"/>
    <text fill="#111111" stroke="#111111" stroke-width="3" x="190" y="139" font-size="14" font-family="serif" text-anchor="middle" xml:space="preserve" id="text2">Overlapping rectangles</text>
    <rect fill-opacity="0" fill="#ffffff" id="r1" height="120" width="100" y="167" x="87" stroke-width="5" stroke="#00dd00"/>
    <rect fill-opacity="0" fill="#ffffff" id="r2" height="90" width="140" y="217" x="147" stroke-width="5" stroke="#0000dd"/>
    <rect fill-opacity="0" fill="#ffffff" id="r1_2" height="70" width="40" y="217" x="147" stroke-width="5" stroke="#dd0000"/>
    <text id="text3" fill="#111111" stroke="#111111" stroke-width="3" x="470" y="52" font-size="14" font-family="serif" text-anchor="middle" xml:space="preserve">Non-overlapping segments on the same line</text>
    <line id="l3" y2="78" x2="400" y1="78" x1="360" stroke-width="5" stroke="#00dd00"/>
    <line id="l4" y2="78" x2="560" y1="78" x1="410" stroke-width="5" stroke="#0000dd"/>
    <text id="text4" fill="#111111" stroke="#111111" stroke-width="3" x="473" y="139" font-size="14" font-family="serif" text-anchor="middle" xml:space="preserve">Non-overlapping rectangles</text>
    <rect id="r3" fill-opacity="0" fill="#ffffff" height="120" width="80" y="167" x="370" stroke-width="5" stroke="#00dd00"/>
    <rect id="r4" fill-opacity="0" fill="#ffffff" height="70" width="50" y="197" x="470" stroke-width="5" stroke="#0000dd"/>
  </g>
</svg>