Obtaining power set in mathematical order-CodePudding

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");
    }

CodePudding user response：

So looking at the list you provided, I would not call that "mathematical order" - what your code produces actually looks more like what I would expect. That's how most algorithms will naturally produce such a power set.

But, fine, say you want it like that. Making an algorithm to naturally produce it in that order is going to be a pain. If you're printing as you create the power set, there's no way around that - you have to print each element in the order your algorithm visits it. However, if you instead return the power set and then print it, it's trivial to sort it however you want in between.

In the below code I (messily) implement my own method to generate the sorted set, just cause arrays are a pain. (Actually everything in Java is a pain.)


public class MyClass {
    public static void main(String args[]) {
      
      List<String> setAsList = Arrays.asList("1", "2", "3");
      List<List<String>> powerSet = powerSetWithPrefix(new ArrayList(), setAsList);
      powerSet.sort( (List<String> l1, List<String> l2) -> l1.size() - l2.size());
      printPowerSet(powerSet);

    }
    static List<List<String>> powerSetWithPrefix(List<String> prefix, List<String> remaining){
        if (remaining.isEmpty()) {
            List<List<String>> ret = new ArrayList();
            ret.add(prefix);
            return ret;
        }
        List<String> tail = remaining.subList(1, remaining.size());
        String head = remaining.get(0);
        List<String> prefixWithout = new ArrayList(prefix);
        List<String> prefixWith = new ArrayList(prefix);
        prefixWith.add(head);
        List<List<String>> powerSet = powerSetWithPrefix(prefixWith, tail);
        powerSet.addAll(powerSetWithPrefix(prefixWithout, tail));
        return powerSet;
    }
    static void printPowerSet(List<List<String>> powerSet){
        System.out.println("Printing powerset:");
        for (List<String> set:  powerSet) {
            System.out.printf("[%s]\n", String.join(", ", set));
        }
    }
}

By separating the powerSet logic from the printing logic, it's easy to control the format of the output without having to wrestle with the algorithm.

If you really need to somehow have an algorithm that will visit shorter lists first, you'd need to write something akin to a breadth-first-search, which would be a lot clunkier.

CodePudding user response：

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