计算一组数字的所有子集

Question

我想找到一组整数的子集.这是带有回溯的"子集和"算法的第一步.我编写了以下代码,但它没有返回正确的答案:

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

例如,如果我想计算set = {1,3,5}的子集我的方法的结果是:

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

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

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

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

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

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

我想要它产生:

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

我认为问题来自part list.removeAll(list); 但我不知道如何纠正它.

Answer 1

你想要的是一个Powerset.这是一个简单的实现:

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

我将举例说明该算法如何适用于以下的powerset {1, 2, 3}:

• 删除{1}并执行powerset for {2, 3};
  • 删除{2}并执行powerset for {3};
    • 删除{3}并执行powerset for {};
      • Powerset {}是{{}};
    • 的幂{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} }.

Answer 2

就在底漆你怎么能解决这个问题:

方法1

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

当然,您必须检查基本情况,即您的号码列表是否为空.

方法2

众所周知,具有n元素的集合具有2^n子集.因此,你可以在二进制数从0向2^n和解释二进制数作为相应子集.请注意,此方法需要具有足够数字位数的二进制数来表示整个集合.

将两种方法之一转换为代码应该是一个不太大的问题.

Answer 3

你的代码真的很混乱,没有解释.

您可以使用位掩码迭代地执行,以确定集合中的数字.例如,从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
}

Answer 4

考虑一个Noob访问者(感谢谷歌)这个问题 - 像我一样
这是一个递归解决方案,适用于简单的主体:

设置= {a,b,c,d,e}
然后我们可以将其分解为{a}+Subset of {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

     }
}

OUTPUT

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

Answer 5

很明显,任何给定集合的子集总数等于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);
    }