从链接列表中查找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

回答

相关问题