16
- March
2015
Calculation of PowerSet on C#

This text explains a binary algorithm to calculate a power set of any sequence. It has a sample code in .

The Wikipedia text can tell you in details about powerset algorithm. Personally it has a clean mathematical description which is hard to transform into programming code. Especially if you try apply it to some more complex case than just a sequence of elements. Further in text I’ll try to explain the basics with a human-friendly language and propose a generic solution to apply to any case.

From the Wikipedia text you should notice that a whole number of sets for a sequence of N elements is 2N (or the binary left shift of 1 to N). Let’s take a sequence of 5 elements. The number of all subsets is 32 (binary 100000). In order to find subsets you can use binary representation of the index of a subset. For example, the subset #3 has binary representation as 000011. Each set bit corresponds to an index in the main set. The corresponding subset for #3 is the sequence {0,1}. Let’s take another number – #16 (001000). The corresponding sequence is {3}. Index of each of subset elements can be obtained by evaluating indexes of set bits.

The whole example in C# you can find in my GitHub repository with tests.

Category:

This site uses Akismet to reduce spam. Learn how your comment data is processed.