I returned to my first love… math ! Back in a day, (no I’m not old !) I loved hitting my head against the wall to find the solution to a problem. And I remember that game theory and combination was really interesting. I recently deal with this techniques so let’s talk about it.
Choosing k elements in n
In this blog post we will use the concept of powerset in our algorithm.
A powerset is a collection that contains all the subset of a set (empty and full sets included). Let’s see an example:
How to generated this powerset without missing any subset ? I tried several ways but to me the most understandable way to do this is by leveraging binary encoding.
Do you remember how to encode 7 in binary ?
- You choose the number of bits : 2⁰ = 1 no 2¹ = 2 no 2²=4 no 2³=8 yes ! So we need 3 bits
- Each bit (from right to left) has a value 1 (2⁰) for the first, 2 (2¹) for the second, 4 (2²) for the third
You got it the result is 111 !
Now count from 0 to 7 on a paper and pay attention to the 1s.
Yes ! you have all the combination to put 1s with a set of 3 elements. If you put in relation the index of the ones you have just created and the index of [a,b,c] you will have your powerset without any doubt. Before coding let’s talk about things that will help us in our code.
How many elements will I have in my powerset ? Same answer other question : How many numbers can be encoded with 3 bits ? you know the answer it’s: 2³ = 8 (from 0 -> 7). For a set of 3 elements, we will have 8 elements in our powerset.
When you convert a number to binary, did you notice that the first element (from right to left) is the only one who can play with the fact that the number is odd or even ? indeed, 2⁰ = 1, 2¹ = 2, 2²= 4. for example 111 = 7 is odd and 110 = 6 is even. We can say that if a number is odd then it’s first bit is 1.
Last tip, For one number we will loop on all the letters and in the same time verify is the number is odd, if it’s odd we keep the letter. The little trick is when we finish with a letter we shift the binary representation of the number to the right.
Now you have everything to understand the code.
This is not the fastest way of doing that though. This code do the same thing 2x time faster on my computer.
I feel less comfortable with this one… Maybe this is because I don’t know the theory behind (union maybe ?) If I found a good article on it, I will let you know ;)
Last thing, to answer the question choose 2 elements in a set of 3 elements, you will have to filter your powerset with only the element of size 2.
I hope you learn something !