C#: Getting Power Set of Given Set of Numbers

This is a quick post on how you can calculate the Power Set of given numbers.

Let’s consider the following array.

int[] numbers = new int[] { 1, 2, 3 };

The Power Set of above would be as follows.

{}
{1}
{2}
{1,2}
{3}
{1,3}
{2,3}
{1,2,3}

Count of Power Set is 1 << CountOfNumbers (or 2 ^ CountOfNumbers).

Here is a simple method to get the Power Set of given integer array.

static IEnumerable<IEnumerable<int>> GetPowerSet(int[] numbers)
{
    List<List<int>> outerList = new List<List<int>>();
 
    int permutationsCount = 1 << numbers.Length;
    int[] permutationNumbers = Enumerable.Range(0, permutationsCount).ToArray();
 
    for (int i = 0; i < permutationsCount; i++)
    {
        List<int> innerList = new List<int>();
 
        for (int j = 0; j < numbers.Length; j++)
        {
            if ((permutationNumbers[i] & (1 << j)) != 0)
            {
                innerList.Add(numbers[j]);
            }
        }
 
        outerList.Add(innerList);
    }
 
    return outerList;
}

We can refactor the code to use LINQ and eliminate some line of codes.

static IEnumerable<IEnumerable<int>> GetPowerSet(int[] numbers)
{
    IEnumerable<IEnumerable<int>> permutations = from permutation in Enumerable.Range(0, 1 << numbers.Length)
                                                 select
                                                     from index in Enumerable.Range(0, numbers.Length)
                                                     where (permutation & (1 << index)) != 0
                                                     select numbers[index];
    return permutations;
}

Happy Coding.

Regards,

Jaliya