如何有效率地生成Java集的冪集？

在Java 中以最佳複雜度取得集合的冪集

集合的冪集是該集合的所有子集的集合。對於包含 n 個元素的集合，冪集包含 2^n 個子集。

讓我們考慮一個 Java 集合：

Set<integer> mySet = new HashSet();
mySet.add(1);
mySet.add(2);
mySet.add(3);</integer>

我們想要寫一個函數 getPowerset 來產生這套。此操作的理想複雜度是​​ O(2^n)。

使用Java 泛型和集合的一種可能實現是：

public static <t> Set<set>> getPowerset(Set<t> originalSet) {
    Set<set>> 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;
}</t></t></t></t></set></t></set></t>

此遞歸解決方案迭代集合的元素，將它們添加到每個子集並產生一個新的子集。它始終保持剩餘元素的冪集。

使用範例輸入進行簡單檢定會產生預期結果：

for (Set<integer> s : getPowerset(mySet)) {
    System.out.println(s);
}</integer>

輸出：

[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

以上是如何有效率地生成Java集的冪集？的詳細內容。更多資訊請關注PHP中文網其他相關文章！