在 Java 中產生集合的冪集
集合的冪集是該集合的所有子集的集合。例如，{1, 2, 3} 的冪集為：
{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3} , {1, 2, 3}, {1}}
假設我們有一個集合Java:
Set<Integer> mySet = new HashSet<Integer>(); mySet.add(1); mySet.add(2); mySet.add(3); Set<Set<Integer>> powerSet = getPowerset(mySet);
如何寫出最適時間複雜度的 getPowerset 函數？
解
powerset 函數的時間複雜度是 O(2^n)，其中 n 是集合中元素的數量。這是因為包含 n 個元素的集合的冪集包含 2^n 個子集。
這是使用泛型和集合的getPowerset 函數的有效實現：
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;
} 測試
讓我們用給定的示例測試getPowerset函數輸入：
Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
for (Set<Integer> s : powerSet(mySet)) {
System.out.println(s);
}這將列印以下輸出：
[] [1] [2] [1, 2] [3] [1, 3] [2, 3] [1, 2, 3]
以上是如何用Java高效生成集合的冪集？的詳細內容。更多資訊請關注PHP中文網其他相關文章！
