從鏈接列表中查找powerset

我正在尋找一些幫助我的Java編程任務。使用鏈表，我需要打印出其功率集。例如，集合{1,2,3}應打印出 {{}，{1} {1,2} {1,3} {1,2,3} {2} {2,3} {3 }}。功率集中的元素數量是2^n。這需要通過調用 HeadNode.PrintPowerSet（）;
其中HeadNode是鏈表中的第一個元素。我已經嘗試了一些東西，沒有什麼工作很好。我認爲最好的方法是遞歸調用該方法，直到達到最終標記，然後向後工作，添加剩下的元素。對不起，我不能發佈更多的代碼或更多的想法，因爲我沒有試過的東西已經很好地工作了。提前致謝。編輯：這是非工作代碼。它返回集合{{1,2,3} {2,3} {3}}從鏈接列表中查找powerset

public RSet powerSet() 
{ 
    if (this == EMPTY_SET) 
     return EMPTY_SET; 

    RSet q = new RSet(); 
    if (q != EMPTY_SET) 
     q.next = next.powerSet(); 
    q = new RSet(this, n, q.next); 

    return q; 
}

EMPTY_SET是結束標記。我試着用手寫出來。它有幫助，但我仍然無法得到它。此類RSet本質上只是一個鏈表節點。

來源

2013-02-11 Jeff

發佈您的非工作代碼。 – 2013-02-11 18:15:31

[這個答案]（http://stackoverflow.com/a/1670871/828193）使用'Set'來做它。我想你可以很容易地使用它來使用'LinkedList' – user000001 2013-02-11 18:20:27

提示：在列表中插入一個空元素。所以你將有'n + 1'元素。然後創建一個遞歸函數，遍歷列表中的所有元素（包括空的元素），並找到所有三種可能的組合。例如：{Empty，Empty，1}將爲{1} .. – Shivam 2013-02-11 18:21:04

只是想迭代所有的數字從0到2^N - 1.每個定義電源設置的元素：

列表定義您設置一個固定的指標。對於每個數字，創建一個新的集合。考慮到二進制格式的數字，如果索引i處的位是1，那麼將索引i處的原始集合中的項目添加到該集合，否則不添加它。

然後，對於每個數字，您將有一組是功率集的一個元素。

int n = list.size(); 

Set<Set<T>> powerSet = new HashSet<Set<T>>(); 

for(long i = 0; i < (1 << n - 1); i++) { 
    Set<T> element = new HashSet<T>(); 
    for(int j = 0; j < n; j++) 
     if((i >> j) % 2 == 1) element.add(list.get(j)); 
    powerSet.add(element); 
} 

return powerSet;

來源

2013-02-11 18:29:40

這個集合可以有字符串或任何隨機數。我只是舉了一個簡單的例子。 – Jeff 2013-02-11 18:36:15

是的，我描述的算法適用於任何類型的對象。 – 2013-02-11 18:41:39

我很欣賞它，但對於此作業，我們不允許使用Set或HashSet。它必須用這個類和遞歸完成。 – Jeff 2013-02-11 19:20:20

從鏈接列表中查找powerset

回答

相關問題