查找集合的所有子集

Question

我需要一种算法来查找集合中元素数为 n 的集合的所有子集。

 S={1,2,3,4...n}

编辑：到目前为止，我无法理解提供的答案。我想逐步解释答案如何找到子集。

例如，

 S={1,2,3,4,5}

你怎么知道 {1} 和 {1,2} 是子集？

有人可以帮我用 C++ 中的一个简单函数来查找 {1,2,3,4,5} 的子集吗

原文由 Rahul Vyas 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

递归地执行此操作非常简单。基本思想是，对于每个元素，子集的集合可以平均分为包含该元素的子集和不包含该元素的子集，否则这两个集合是相等的。

• 对于 n=1，子集的集合是 {{}, {1}}
• 对于 n>1，找到 1,…,n-1 的子集的集合并制作两个副本。对于其中一个，将 n 添加到每个子集。然后取两个副本的并集。

编辑 使其一目了然：

• {1} 的子集是 {{}, {1}}
• 对于 {1, 2}，取 {{}, {1}}，每个子集加 2 得到 {{2}, {1, 2}} 并取与 {{}, {1}} 的并集得到{{}、{1}、{2}、{1、2}}
• 重复直到达到 n

原文由 Michael Borgwardt 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

基于上述“Michael Borgwardt”算法的无递归Java 版本。

public static List powerset(List array) { List perms = new ArrayList(); if(array.size()==0) { perms.add(new ArrayList());退货烫发； } 返回幂集（数组，烫发）； }

 public static List<List<Integer>> powerset(List<Integer> array, List<List<Integer>> perms) {

    for(int i=0;i<array.size();i++){
        perms.add(Arrays.asList(array.get(i)));
        int x=perms.size();
        for(int j=0;j<x;j++){
            List<Integer> tmp = new ArrayList<Integer>(perms.get(j));
            if(!(tmp.size()==1 && tmp.get(0)==array.get(i))){
                tmp.add(array.get(i));
                perms.add(tmp);
            }
        }
    }
    perms.add(new ArrayList<Integer>());
return perms;

}

原文由 ankidaemon 发布，翻译遵循 CC BY-SA 4.0 许可协议