Combination of Numbers

Introduction

I already have one post on this blog which explains the permutations code, now its time for the combinations.

The idea behind Combination of Numbers

Combination by definition is a concept of discrete mathematics which essentially relates to the act of selecting a list of items from a collection. For e.g. If I have to pick up 3 fruits from a basket of 10 fruits then what all ways are there to pick them up? Combinations is the answer to this question.

Let us say that I picked an Apple, a Banana and a Strawberry from the basket, then it really won’t matter in what order I pick up these fruits.

This whole thing works good if we have ten distinct fruits so that we do not pick up the same fruit again. The other variation where we have repeated fruits can be discussed later in some other post.

The mathematical formula for Combinations is represented as C(n, r) , where n is the total number of fruits in the basket and r is the total fruits to pick.

In the above example n equals to 10 and r equals to 3. There are many ways to solve this problem but here I want to highlight a very specific way which depends on bit wise representation.

Let us look at the below numbers :
Combination of Numbers
Point worth noticing is that all the above numbers have unique four bit representations. Let us say that we had four distinct elements in an array and we needed all possible combinations C(4,0), C(4,1), C(4,2), C(4,3) and C(4,4) then the above bit representations will give us the answer.

The number 0000 suggests that do not pick any element from the array.
The number 0001 suggests that we only pick the element at index 4 of the array.
The number 0010 suggests that we only pick the element at index 3 of the array.
The number 0011 suggests that we pick the elements at index 3 and 4 of the array.

Basically, we choose elements at those indices from the array which have a 1 in the corresponding bit representation. To explain it further, we need an example.
Combination of Numbers
Corresponding to number 07 the bit representation is (0111). So the corresponding combination is for C(4, 3) and it tells that we need to pick up elements at indices 2, 3 and 4 from our fruits array.
So one of the C(4,3) combination is GRAPE, BANANA and ORANGE.

If we want to find all possible C(4, 3) then we pick up all those numbers whose bit representation contains three 1s.
Similarly, if we want to find C(4,2) then we pick up all those numbers whose bit representation contains two 1s.

Lets figure out C(4,3), the numbers of interest would be 07, 11, 13, 14, basically four numbers. Also, C(4, 3) equals to 4. So the four combinations would be:
0111 – GRAPE, BANANA and ORANGE.
1011 – APPLE, BANANA and ORANGE.
1101 – APPLE, GRAPE and ORANGE.
1110 – APPLE, GRAPE and BANANA.

Lets do it one more time, figure out C(4,2), the numbers of interest are 03, 05, 06, 09, 10, 12 basically six numbers. Also, C(4, 2) equals to 6. So the six combinations would be:
0011 – BANANA, ORANGE
0101 – GRAPE, ORANGE
0110 – GRAPE, BANANA
1001 – APPLE, ORANGE
1010 – APPLE, BANANA
1100 – APPLE, GRAPE

Now that wee understood, how to find combinations, it is pretty obvious that for combinations of a set of four elements we need to evaluate 16 numbers. Similarly for three elements we need to evaluate 8 numbers. Basically if we need to find all combinations of a number N then we need to evaluate 2N numbers.

Pseudo Code

Source Code

You can do various stuffs with this code, you can choose to print only one set from all the sets, like C(4,2) and not all the combinations.

Don’t forget to subscribe to TechieMe to get updates on latest posts.