« Back to blog

Combinations

I like things to be simple. And i like it better when i have simple alternatives to complicated solutions. One such problem was that of finding Combinations or make all possible selections from a given set of things. I had this as a part of my course in my second year of engineering. Most of us solved it using a weird recursive approach, which has haunted me till date. Never quite got the complete grasp of it. Well, that is because i found a simpler, sweeter and much more elegant way of finding C(n,n). Check this out: If you ever observe the bit patterns of binary numbers you will notice a pattern. You will realize that the position of the 1's in the bit form of a number sequence actually indicates which thing has been selected. Assume that there are 3 objects, of which all combinations have to be derived. Step 1: Write down all the numbers in sequence in the binary format, starting from 000 to 111 (since there are 3 objects, if 4 objects were to be selected write down the sequence from 0000 to 1111).

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

Step 2: Since there are 3 columns, mark each of them with on object. Eg: if the objects were A, B and C: the demarcation would look something like this:

A B C

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

Step 3: Next to each binary number, for every 1 (one) in the number, write the name of the column (the object A, B or C). For every zero do nothing.

A B C

0 0 0 - {}

0 0 1 - {C}

0 1 0 - {B}

0 1 1 - {B,C}

1 0 0 - {A}

1 0 1 - {A,C}

1 1 0 - {A,B}

1 1 1 - {A,B,C}

Step 4: The selections or the combinations (given the curly braces) according to the positions of the 1's in the bit pattern from 000 to 111, happen to be nothing but all the combinations for the objects A, B and C. The first selection is just the null set, i.e. nothing is selected.

{{} , {C}, {B}, {B,C}, {A}, {A,C}, {A,B}, {A,B,C}}

There you are! A simple and elegant method of finding combinations. Now after i found this method i never had the slightest interest to get into the intricacies of a complex recursive approach. And the best part is that all this could be implemented with relative ease using simple bit operations, if statements and for loops.

This was also the real reason, as to why my data structures and algorithms professor found it so difficult to teach me recursion, even she did not see the point of teaching it after i told her about this approach. :D