在Java 中以最佳複雜度取得集合的冪集
集合的冪集是該集合的所有子集的集合。對於包含 n 個元素的集合，冪集包含 2^n 個子集。
讓我們考慮一個 Java 集合：
Set<Integer> mySet = new HashSet<>(); mySet.add(1); mySet.add(2); mySet.add(3);
我們想要寫一個函數 getPowerset 來產生這套。此操作的理想複雜度是 O(2^n)。
使用Java 泛型和集合的一種可能實現是：
public static <T> Set<Set<T>> getPowerset(Set<T> originalSet) {
Set<Set<T>> sets = new HashSet<>();
if (originalSet.isEmpty()) {
sets.add(new HashSet<>());
return sets;
}
List<T> list = new ArrayList<>(originalSet);
T head = list.get(0);
Set<T> rest = new HashSet<>(list.subList(1, list.size()));
for (Set<T> set : getPowerset(rest)) {
Set<T> newSet = new HashSet<>();
newSet.add(head);
newSet.addAll(set);
sets.add(newSet);
sets.add(set);
}
return sets;
}此遞歸解決方案迭代集合的元素，將它們添加到每個子集並產生一個新的子集。它始終保持剩餘元素的冪集。
使用範例輸入進行簡單檢定會產生預期結果：
for (Set<Integer> s : getPowerset(mySet)) {
System.out.println(s);
}輸出：
[] [1] [2] [1, 2] [3] [1, 3] [2, 3] [1, 2, 3]
以上是如何有效率地生成Java集的冪集？的詳細內容。更多資訊請關注PHP中文網其他相關文章！
