# 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 C#.

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 you can find in my GitHub repository with tests.

Tags:

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

## Speeding up calculation of an average in continuous processesSpeeding up calculation of an average in continuous processes

Processing big sets of data can cause a low performance due to inefficient calculations. In order to overcome this issue we should rewrite calculations in a way which allows getting ## String Expression CalculatorString Expression Calculator

Parsing of math equations from text expressions is the interesting thing. This task is close to LL parsing but can be solved in different ways. This approach tends to be the simplest