按数学顺序获取幂集

Question

{1,2,3}的幂集是：

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

我有一个java字符串数组，

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

如何按数学顺序打印此数组的幂集？（我试过位操作方法，它没有按该顺序给出解决方案！）

我的位操作方法！没有给出所需的结果！

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

Answer 1

这是一个有趣的算法，高德纳考虑过。这实际上比听起来容易得多。

我正在解释命令。按照基数的顺序输出子集（从空集开始）。在该顺序中，基于所包含成员的位置（{1,2}在{2,3}之前），它们在词汇上相互关联。

下面的示例显示了一组 4 个对象，因为 3 个对象并不能完全揭示正在发生的事情。

它使用一组< code>boolean标志来表示成员资格。在每个步骤中，在至少一个< code>true标志之后寻找一个< code>false标志。如果找到，则将< code>true置位，并将真标志数减1设置回起始值。如果因为设置了所有标志而没有找到，我们就输出完整的标志集。所以结束吧。否则，从具有更多成员的第一个子集开始(计数1标志集)。

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

Answer 2

因此，查看您提供的列表，我不会将其称为“数学顺序” - 您的代码生成的实际上看起来更像我所期望的。这就是大多数算法自然产生这种功率集的方式。

但是，好吧，说你想要那样。制作一个算法来自然地按顺序生成它将是一件痛苦的事。如果在创建幂集时进行打印，那就没有办法了——必须按照算法访问的顺序打印每个元素。然而，如果您返回功率集，然后打印它，那么在两者之间进行排序是很简单的。

在下面的代码中，我（混乱地）实现了我自己的方法来生成排序集，只是因为数组很痛苦。（实际上Java中的一切都是痛苦的。）

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

通过将powerSet逻辑从打印逻辑中分离出来，可以很容易地控制输出的格式，而不必纠结于算法。

如果你真的需要有一个算法先访问较短的列表，你需要写一些类似于广度优先搜索的东西，这会很笨拙。