计算一组数字的所有子集

43

我想找到一组整数的子集。这是“子集之和”算法(回溯法)的第一步。我已经编写了以下代码,但它没有返回正确的答案:

BTSum(0, nums);
///**************
ArrayList<Integer> list = new ArrayList<Integer>();

public static ArrayList<Integer> BTSum(int n, ArrayList<Integer> numbers) {
    if (n == numbers.size()) {
        for (Integer integer : list) {
            System.out.print(integer+", ");
        }
        System.out.println("********************");
        list.removeAll(list);
        System.out.println();
    } else {
        for (int i = n; i < numbers.size(); i++) {
            if (i == numbers.size() - 1) {
                list.add(numbers.get(i));
                BTSum(i + 1, numbers);
            } else {
                list.add(numbers.get(i));
                for (int j = i+1; j < numbers.size(); j++)
                BTSum(j, numbers);
            }
        }
    }

    return null;
}
例如,如果我想计算集合{1, 3, 5}的子集 我的方法的结果是:
 1, 3, 5, ********************

 5, ********************

 3, 5, ********************

 5, ********************

 3, 5, ********************

 5, ********************

我希望它能生成:

1, 3, 5 
1, 5
3, 5
5

我认为问题出在这部分代码 list.removeAll(list); 但我不知道如何修改它。


4
http://www.cs.princeton.edu/introcs/23recursion/Combinations.java.html - Mihai Toader
2
这是一份作业吗?如果是的话,请在 Stack Overflow 上搜索,你的同学们可能已经问过了。花些时间进行调试。 - Nishant
9
输出结果不应该包含1、3和1、3吗? - phimuemue
可能是重复的问题:如何找到给定数组的所有可能子集? - moinudin
http://google.github.io/guava/releases/snapshot/api/docs/com/google/common/collect/Sets.html#powerSet(java.util.Set) - avianey
显示剩余2条评论
16个回答

89

你想要的是叫做幂集。这是一个简单的实现:

public static Set<Set<Integer>> powerSet(Set<Integer> originalSet) {
        Set<Set<Integer>> sets = new HashSet<Set<Integer>>();
        if (originalSet.isEmpty()) {
            sets.add(new HashSet<Integer>());
            return sets;
        }
        List<Integer> list = new ArrayList<Integer>(originalSet);
        Integer head = list.get(0);
        Set<Integer> rest = new HashSet<Integer>(list.subList(1, list.size()));
        for (Set<Integer> set : powerSet(rest)) {
            Set<Integer> newSet = new HashSet<Integer>();
            newSet.add(head);
            newSet.addAll(set);
            sets.add(newSet);
            sets.add(set);
        }
        return sets;
    }
我将给你一个例子来解释如何求解集合{1, 2, 3}的幂集的算法:
  • 移除{1},并对{2, 3}执行幂集算法;
    • 移除{2},并对{3}执行幂集算法;
      • 移除{3},并对空集执行幂集算法;
        • 空集的幂集为{{}};
      • {3}的幂集为3{{}}的组合 = { {}, {3} };
    • {2, 3}的幂集为{2}{ {}, {3} }的组合 = { {}, {3}, {2}, {2, 3} };
  • {1, 2, 3}的幂集为{1}{ {}, {3}, {2}, {2, 3} }的组合 = { {}, {3}, {2}, {2, 3}, {1}, {3, 1}, {2, 1}, {2, 3, 1} }.

这是2^n的时间复杂度吗? - user3335040
@user3335040,是的,因为您总是需要生成2^n个集合。 - João Silva
我无法理解步骤“{2, 3}的幂集”与“{ {}, {3} }”的组合等于“{ {}, {3}, {2}, {2, 3} }”的逻辑;因为在前一步中,头部是3,而剩余部分为空。 - Harish
@Harish 逻辑是前一步骤加上前面的所有内容和新元素。所以你有 {{}, {3}},它保留在新集合中,并且你还要将其中的每个元素加2并组合在一起。因此,你会得到 {} + 2 = {2}{3} + 2 = {2,3}。与之前的内容结合,你会得到 {{} , {3}, {2}, {2,3}} - cheenbabes
这是O(n^2)的解法。有没有可能得到一个时间复杂度更好的解法? - Rizwan_Khan

24

这里给出两种解决问题的方法:

方法一

  • 取出数字列表中的第一个元素
  • 从剩余数字列表中(即不包含所选数字的数字列表)生成所有子集 => 递归!
  • 对于在上一步找到的每个子集,将子集本身和与步骤1中选择的元素连接后得到的子集添加到输出结果中。

当然,你还要检查基本情况,即数字列表是否为空。

方法二

众所周知,具有n个元素的集合有2^n个子集。因此,您可以使用二进制从02^n进行计数,并将二进制数解释为相应的子集。请注意,此方法需要具有足够位数的二进制数才能表示整个集合。

把其中一种方法转换成代码应该不会太难。


15

你的代码非常令人困惑,没有任何解释。

你可以使用位掩码进行迭代,以确定集合中包含哪些数字。每个数字从0到2^n在其二进制表示中都会产生一个唯一的子集,例如

对于n = 3:

i = 5 -> 101以二进制表示,选择第一个和最后一个元素 i = 7 -> 111以二进制表示,选择前3个元素

假设有n个元素(n < 64),毕竟如果n大于64,你将永远运行它。

for(long i = 0; i < (1<<n); i++){
    ArrayList<Integer> subset = new ArrayList<Integer>();
    for(int j = 0; j < n; j++){
        if((i>>j) & 1) == 1){ // bit j is on
            subset.add(numbers.get(j));
        }
    }
    // print subset
}

你能详细解释一下 f((i>>j) & 1) == 1) 吗?我知道你正在将 i 向右移动 j 位,并在 i 的二进制表示中添加 j 个零。我也明白按位与运算符是在比较 i >> j 和 1,看看在 i >> j 和 1 之间是否所有位都处于打开状态。但我不明白为什么这个操作是知道何时添加子集的知识。 - Brian Ogden
@BrianOgden (i>>j)&1==1 只是测试 i 中的第 j 位是否设置。数字中的第 j 位对应于子集是否包含第 j 个对象。而 i 循环从 0 到 2<sup>n</sup>-1。 - Michael Anderson
谢谢@MichaelAnderson,这有些帮助,但为什么第j位对应于包含第j个对象的子集呢? - Brian Ogden
不是包含第j个对象的子集 - 因为可能有多个。如果在i中的第j位被设置,则第i个子集包含第j个对象。我在您单独提出的问题的答案中提供了更完整的解释(http://stackoverflow.com/questions/33337317/using-distinct-binary-numbers-to-find-subsets-of-a-given-set)。 - Michael Anderson

10

考虑到一个类似我的(感谢Google)新手访问者对于这个问题 - 像我一样
这里有一个递归解决方案,它基于简单的原则:

集合 = {a,b,c,d,e}
然后我们可以将其分解为 {a} + {b,c,d,e}的子集

public class Powerset{
     String str = "abcd"; //our string
     public static void main(String []args){
        Powerset ps = new Powerset();
        for(int i = 0; i< ps.str.length();i++){ //traverse through all characters
            ps.subs("",i);
        }
     }

     void subs(String substr,int index)
     {
         String s = ""+str.charAt(index); //very important, create a variable on each stack
         s = substr+s; //append the subset so far
         System.out.println(s); //print

         for(int i=index+1;i<str.length();i++)
           subs(s,i); //call recursively

     }
}

输出

a
ab
abc
abcd
abd
ac
acd
ad
b
bc
bcd
bd
c
cd
d

4
简洁优雅的解决方案,实现+1。 - Luke Taylor
1
喜欢这个解决方案 - 毫无疑问,这是正确的方法,感谢您。如果我理解正确,递归工作的思考方式是:我们从a、b、c、d作为最小的子集开始。然后当我们想要查看每个更大的子集时,我们说a->ab、ac、ad,然后b->bc、bd(不是ab,因为我们已经有了它),依此类推,这就是为什么前进索引是正确的方法。再次感谢。 - shimi_tap
是的....我根据这样的逻辑编写代码,即将"ab"存储在递归堆栈中,然后使用它并将"c"附加到其中...因此,在新的递归堆栈上输出"abc"。打印它并继续附加! :) - NoobEditor

4
显然,任意给定集合的子集总数等于2^(集合中元素的数量)。如果集合为A = {1, 2, 3},则A的子集为:{ }, { 1 }, { 2 }, { 3 }, { 1, 2 }, { 1, 3 }, { 2, 3 }, { 1, 2, 3 }。如果我们将其看作二进制数字,则为:{ 000 }, { 001 }, { 010 }, { 011 }, { 100 }, { 101 }, { 110 }, { 111 }。考虑以上内容:
static void subSet(char[] set) {
        int c = set.length;

        for (int i = 0; i < (1 << c); i++) {
            System.out.print("{");
            for (int j = 0; j < c; j++) {
                if ((i & (1 << j)) > 0) {
                    System.out.print(set[j] + " ");
                }
            }
            System.out.println("}");
        }
    }

    public static void main(String[] args) {
        char c[] = {'a', 'b', 'c'};
        subSet(c);
    }

2
public static void printSubsets(int[] arr) {
    for (int start = 0; start < arr.length; start++) { // iterate through each element of the array
        for (int i = 0; i < arr.length - start; i++) { // find number of subsets for the element
            int[] tmp = new int[i + 1]; // calculate a temporal array size 
            for (int j = 0; j < tmp.length; j++) { // populate the array with corresponding elements
                tmp[j] = arr[start + j];
            }
            System.out.println(Arrays.toString(tmp));
        }
    }
}

1
我想知道这个解决方案的时间复杂度。 - saintlyzero
这个解决方案没有列出所有可能的子集,因此是错误的。 - Gi1ber7

2

根据我今天学到的内容,这是Java解决方案。它基于递归

public class Powerset {

    public static void main(String[] args) {
        final List<List<String>> allSubsets = powerSet(Arrays.asList(1, 2, 3, 4), 0);
        for (List<String> subsets : allSubsets) {
            System.out.println(subsets);
        }
    }

    private static List<List<String>> powerSet(final List<Integer> values,
                                               int index) {
        if (index == values.size()) {
            return new ArrayList<>();
        }
        int val = values.get(index);
        List<List<String>> subset = powerSet(values, index + 1);
        List<List<String>> returnList = new ArrayList<>();
        returnList.add(Arrays.asList(String.valueOf(val)));
        returnList.addAll(subset);
        for (final List<String> subsetValues : subset) {
            for (final String subsetValue : subsetValues) {
                returnList.add(Arrays.asList(val + "," + subsetValue));
            }
        }
        return returnList;
    }
}

运行它会得到以下结果:
[1]
[2]
[3]
[4]
[3,4]
[2,3]
[2,4]
[2,3,4]
[1,2]
[1,3]
[1,4]
[1,3,4]
[1,2,3]
[1,2,4]
[1,2,3,4]

2
private static void findSubsets(int array[])
{
  int numOfSubsets = 1 << array.length; 

  for(int i = 0; i < numOfSubsets; i++)
 {
    int pos = array.length - 1;
   int bitmask = i;

   System.out.print("{");
   while(bitmask > 0)
   {
    if((bitmask & 1) == 1)
     System.out.print(array[pos]+",");
    bitmask >>= 1;
    pos--;
   }
   System.out.print("}");
 }
}

1

我实际上正在尝试解决这个问题,并在之前的帖子中得到了@phimuemue的算法。这是我实现的内容。希望这能起作用。

/**
*@Sherin Syriac
*
*/

import java.util.ArrayList;
import java.util.List;

public class SubSet {
    ArrayList<List<Integer>> allSubset = new ArrayList<List<Integer>>();

    /**
     * @param args
     */
    public static void main(String[] args) {
        SubSet subSet = new SubSet();
        ArrayList<Integer> set = new ArrayList<Integer>();
        set.add(1);
        set.add(2);
        set.add(3);
        set.add(4);
        subSet.getSubSet(set, 0);
        for (List<Integer> list : subSet.allSubset) {
            System.out.print("{");
            for (Integer element : list) {
                System.out.print(element);
            }
            System.out.println("}");
        }

    }

    public void getSubSet(ArrayList<Integer> set, int index) {
        if (set.size() == index) {
            ArrayList<Integer> temp = new ArrayList<Integer>();
            allSubset.add(temp);
        } else {
            getSubSet(set, index + 1);
            ArrayList<List<Integer>> tempAllSubsets = new ArrayList<List<Integer>>();
            for (List subset : allSubset) {
                ArrayList<Integer> newList = new ArrayList<Integer>();
                newList.addAll(subset);
                newList.add(set.get(index));
                tempAllSubsets.add(newList);
            }

            allSubset.addAll(tempAllSubsets);
        }

    }

}

1
// subsets for the set of 5,9,8

import java.util.ArrayList;
import java.util.List;

public class Subset {
    public static void main(String[] args) {
    List<Integer> s = new ArrayList<Integer>();
    s.add(9);
    s.add(5);
    s.add(8);
    int setSize = s.size();
    int finalValue = (int) (Math.pow(2, setSize));
    String bValue = "";
    for (int i = 0; i < finalValue; i++) {
        bValue = Integer.toBinaryString(i);
        int bValueSize = bValue.length();
        for (int k = 0; k < (setSize - bValueSize); k++) {
            bValue = "0" + bValue;
        }
        System.out.print("{ ");
        for (int j = 0; j < setSize; j++) {
            if (bValue.charAt(j) == '1') {
                System.out.print((s.get(j)) + " ");
            }
        }
        System.out.print("} ");
    }
}
}


//Output : { } { 8 } { 5 } { 5 8 } { 9 } { 9 8 } { 9 5 } { 9 5 8 } 

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接