0

我正在为我的 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}}

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 这个类本质上只是一个链表节点。

4

1 回答 1

1

只需迭代从 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-11T18:29:40.147 回答