从链接列表中查找电源集

Question

我正在寻找一些关于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本质上只是一个链表节点。

Answer 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;