获得一组Java中的幂 [英] Obtaining a powerset of a set in Java
本文介绍了获得一组Java中的幂的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
的幂 {1,2,3}
是:
{{},{2},{3},{2,3},{1,2},{1,3},{1,2,3},{1} }
让我们说我有一个设置
在Java中:
Let's say I have a Set
in Java:
Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
Set<Set<Integer>> powerSet = getPowerset(mySet);
我怎样写功能getPowerset,复杂性的最好的顺序? (我想可能是O(2 ^ n)的。)
How do I write the function getPowerset, with the best possible order of complexity? (I think it might be O(2^n).)
推荐答案
是的,这是 O(2 ^ n)的
事实上,因为你需要生成,那么, 2的n次方
可能的组合。这里有一个工作的实施,使用泛型和集合:
Yes, it is O(2^n)
indeed, since you need to generate, well, 2^n
possible combinations. Here's a working implementation, using generics and sets:
public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
Set<Set<T>> sets = new HashSet<Set<T>>();
if (originalSet.isEmpty()) {
sets.add(new HashSet<T>());
return sets;
}
List<T> list = new ArrayList<T>(originalSet);
T head = list.get(0);
Set<T> rest = new HashSet<T>(list.subList(1, list.size()));
for (Set<T> set : powerSet(rest)) {
Set<T> newSet = new HashSet<T>();
newSet.add(head);
newSet.addAll(set);
sets.add(newSet);
sets.add(set);
}
return sets;
}
和测试,给你的例子输入:
And a test, given your example input:
Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
for (Set<Integer> s : SetUtils.powerSet(mySet)) {
System.out.println(s);
}
这篇关于获得一组Java中的幂的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文