javaalgorithmpowerset

Printing all possible subsets of a list


I have a List of elements (1, 2, 3), and I need to get the superset (powerset) of that list (without repeating elements). So basically I need to create a List of Lists that looks like:

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

What is the best (simplicity > efficiency in this case, the list won't be huge) way to implement this? Preferably in Java, but a solution in any language would be useful.


Solution

  • Use bitmasks:

    int allMasks = (1 << N);
    for (int i = 1; i < allMasks; i++)
    {
        for (int j = 0; j < N; j++)
            if ((i & (1 << j)) > 0) //The j-th element is used
               System.out.print((j + 1) + " ");
    
        System.out.println();
    }
    

    Here are all bitmasks:

    1 = 001 = {1}
    2 = 010 = {2}
    3 = 011 = {1, 2}
    4 = 100 = {3}
    5 = 101 = {1, 3}
    6 = 110 = {2, 3}
    7 = 111 = {1, 2, 3}
    

    You know in binary the first bit is the rightmost.