的幂集{1, 2, 3}是:
{1, 2, 3}
{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}
假设我有一个SetJava语言:
Set
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)。)
是的,O(2^n)的确如此,因为您需要生成2^n可能的组合。这是一个使用泛型和集合的有效实现:
O(2^n)
2^n
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; }
根据您的示例输入进行测试:
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); }