获得一组Java中的幂 [英] Obtaining a powerset of a set in 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屋！