3 回答

TA貢獻1712條經驗 獲得超3個贊
您想要的就是Powerset。這是一個簡單的實現:
public static Set<Set<Integer>> powerSet(Set<Integer> originalSet) {
Set<Set<Integer>> sets = new HashSet<Set<Integer>>();
if (originalSet.isEmpty()) {
sets.add(new HashSet<Integer>());
return sets;
}
List<Integer> list = new ArrayList<Integer>(originalSet);
Integer head = list.get(0);
Set<Integer> rest = new HashSet<Integer>(list.subList(1, list.size()));
for (Set<Integer> set : powerSet(rest)) {
Set<Integer> newSet = new HashSet<Integer>();
newSet.add(head);
newSet.addAll(set);
sets.add(newSet);
sets.add(set);
}
return sets;
}
我將為您提供一個示例,以說明該算法如何用于的冪集{1, 2, 3}:
移除{1}并執行powerset {2, 3};
移除{2}并執行powerset {3};
移除{3}并執行powerset {};
的冪集{}為{{}};
的冪{3}被3聯合{{}}= { {}, {3} };
的冪{2, 3}被{2}聯合{ {}, {3} }= { {}, {3}, {2}, {2, 3} };
的冪{1, 2, 3}被{1}聯合{ {}, {3}, {2}, {2, 3} }= { {}, {3}, {2}, {2, 3}, {1}, {3, 1}, {2, 1}, {2, 3, 1} }。

TA貢獻1785條經驗 獲得超4個贊
就在底漆你怎么能解決這個問題:
方法1
將號碼列表中的第一個元素
從剩余的號碼列表(即沒有選定號碼列表的號碼列表)生成所有子集=>遞歸!
對于上一步中找到的每個子集,將子集本身以及與在步驟1中選擇的元素連接的子集添加到輸出中。
當然,您必須檢查基本情況,即您的號碼列表是否為空。
方法2
眾所周知,帶有n元素的集合具有2^n子集。因此,您可以算出從0到2^n的二進制數,并將二進制數解釋為相應的子集。請注意,此方法需要一個二進制數,該二進制數必須具有足夠的數字來表示整個集合。
將兩種方法之一轉換為代碼應該不是一個太大的問題。

TA貢獻1796條經驗 獲得超7個贊
您的代碼確實令人困惑,沒有解釋。
您可以使用位掩碼進行迭代操作,該位掩碼確定集合中的數字。從0到2 ^ n的每個數字都以其二進制表示形式給出一個唯一的子集,例如
對于n = 3:
i = 5-> 101以二進制形式,選擇第一個和最后一個元素i = 7-> 111以二進制形式,選擇前3個元素
假設有n個元素(n <64,如果n大于64,則將永遠運行該元素)。
for(long i = 0; i < (1<<n); i++){
ArrayList<Integer> subset = new ArrayList<Integer>();
for(int j = 0; j < n; j++){
if((i>>j) & 1) == 1){ // bit j is on
subset.add(numbers.get(j));
}
}
// print subset
}
添加回答
舉報