3 回答
TA贡献1712条经验 获得超3个赞
您想要的就是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;
}
我将为您提供一个示例,以说明该算法如何用于的幂集{1, 2, 3}:
移除{1}并执行powerset {2, 3};
移除{2}并执行powerset {3};
移除{3}并执行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} }。
TA贡献1785条经验 获得超4个赞
就在底漆你怎么能解决这个问题:
方法1
将号码列表中的第一个元素
从剩余的号码列表(即没有选定号码列表的号码列表)生成所有子集=>递归!
对于上一步中找到的每个子集,将子集本身以及与在步骤1中选择的元素连接的子集添加到输出中。
当然,您必须检查基本情况,即您的号码列表是否为空。
方法2
众所周知,带有n元素的集合具有2^n子集。因此,您可以算出从0到2^n的二进制数,并将二进制数解释为相应的子集。请注意,此方法需要一个二进制数,该二进制数必须具有足够的数字来表示整个集合。
将两种方法之一转换为代码应该不是一个太大的问题。
TA贡献1796条经验 获得超7个赞
您的代码确实令人困惑,没有解释。
您可以使用位掩码进行迭代操作,该位掩码确定集合中的数字。从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
}
添加回答
举报