Obtaining power set in mathematical order

The powerset of {1, 2, 3} is:

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

I have a String array in java,

        String elements={"apple","mango","banana"};
        String set[]=elements.split("[ ,]+");

How do I print the power set of this array in the Mathematical order? (I have tried bit manipulation method, it does not gives the solution in that order! )

My bit manipulation method! Did not give the required result!

static void printPowerSet(String[] set) {
        long pset = (long) Math.pow(2, set.length);
        System.out.print("Power Set is \n{");
        for (int i = 0; i < pset; i++) {
            System.out.print("{");
            for (int j = 0; j < set.length; j++) {
                if ((i & (1 << j)) > 0){
                    System.out.print(set[j] + " ");
                    
                }
                if (i == 0 && j==0 )
                    System.out.print(" ");
            }
            System.out.println("}");
        }
        System.out.println(" } \n");
    }

This is a fun algorithm and one Knuth considers. It's actually far easier than it sounds.

I'm interpreting the order to be:

Output the subsets in order of cardinality (starting with the empty set then singletons then pairs and so on).

Within that order then further order them lexically with each other based on position of the included members ({1,2} is before {1,3} is before {2,3}).

The example below shows a set of 4 objects because 3 objects doesn't quite reveal what's going on...

It works on an array of boolean flags to indicate membership. At each step look for a false flag after at least one true flag. If found then set that false flag to true and set the number of true flags counted so far minus one back to the start.

If not found because all flags are set, we've just output the full set. So finish. Otherwise it wasn't found because the set flags have migrated to the end, so start with the first subset with more members (the count+1 flags set).

You can comment back in the line dump(flags,fruit); to see the fruit. But the flags output is the most illuminating.

class Subsets
{
    public static boolean advance(boolean[] flags){
        int count=0;
        for(int i=0;i<flags.length;++i){
            if(flags[i]){
                ++count;
            }else{
                if(count>0){
                    flags[i]=true;
                    for(int j=0;j<(count-1);++j){
                        flags[j]=true;
                    }
                    for(int j=(count-1);j<i;++j){
                        flags[j]=false;
                    }
                    return true;
                }
            }
        }
        //Fell off the end.
        if(count==flags.length){
            return false; // All flags set.
        }
        //Rack 'em up for subsets larger than the ones we've finished.
        for(int i=0;i<=count;++i){
            flags[i]=true;
        }
        for(int i=count+1;i<flags.length;++i){
            flags[i]=false;
        }
        return true;
    }
    
    public static void dump(boolean[] flags){
        for(int i=0;i<flags.length;++i){
            System.out.print(flags[i]?'Y':'N');
        }
        System.out.println();
    }
    
    public static void dump(boolean[] flags,String[] items){
        for(int i=0;i<flags.length;++i){
            if(flags[i]){
                System.out.print(items[i]+" ");
            }
        }
        System.out.println();
    }
    
    public static void main (String[] args) throws java.lang.Exception
    {
        String[] fruit={"Apple","Mango","Banana","Pear"};
        boolean[] flags=new boolean [4];
        do{
            dump(flags);
            //dump(flags,fruit);
        }while(advance(flags));
    }
}

Expected Output:

NNNN
YNNN
NYNN
NNYN
NNNY
YYNN
YNYN
NYYN
YNNY
NYNY
NNYY
YYYN
YYNY
YNYY
NYYY
YYYY

Refer to: Art of Computer Programming, Volume 4A, The: Combinatorial Algorithms, Part 1.