生成生成集的算法

给定此输入：[1,2,3,4]

我想生成一组跨越集：

[1] [2] [3] [4]
[1] [2] [3,4]
[1] [2,3] [4]
[1] [3] [2,4]
[1,2] [3] [4]
[1,3] [2] [4]
[1,4] [2] [3]
[1,2] [3,4]
[1,3] [2,4]
[1,4] [2,3]
[1,2,3] [4]
[1,2,4] [3]
[1,3,4] [2]
[2,3,4] [1]
[1,2,3,4]

每个集合都包含原始集合的所有元素，排列后出现在唯一的子集中。产生这些集合的算法是什么？我尝试过使用选择、排列、组合、幂集等的 Python 生成器函数，但无法获得正确的组合。

2009 年 1 月 20 日

这不是一个家庭作业问题。这是我正在为 www.projecteuler.net 问题#118 所做的改进答案。我已经有了一个缓慢的解决方案，但想出了一个更好的方法——除了我不知道如何进行跨越集。

当我从就职派对回来时，我会发布我的代码。

2009 年 1 月 21 日

这是我最终使用的算法：

def spanningsets(items):
    if len(items) == 1:
        yield [items]
    else:
        left_set, last = items[:-1], [items[-1]]
        for cc in spanningsets(left_set):
            yield cc + [last]
            for i,elem in enumerate(cc):
                yield cc[:i] + [elem + last] + cc[i+1:]

@Yuval F：我知道如何进行动力组。这是一个简单的实现：

def powerset(s) :
    length = len(s)
    for i in xrange(0, 2**length) :
        yield [c for j, c in enumerate(s) if (1 << j) & i]
    return

这应该有效，尽管我还没有对其进行足够的测试。

def spanningsets(items):
    if not items: return
    if len(items) == 1:
        yield [[items[-1]]]
    else:
        for cc in spanningsets(items[:-1]):
            yield cc + [[items[-1]]]
            for i in range(len(cc)):
                yield cc[:i] + [cc[i] + [items[-1]]] + cc[i+1:]

for sset in spanningsets([1, 2, 3, 4]):
    print ' '.join(map(str, sset))

Output:

[1] [2] [3] [4]
[1, 4] [2] [3]
[1] [2, 4] [3]
[1] [2] [3, 4]
[1, 3] [2] [4]
[1, 3, 4] [2]
[1, 3] [2, 4]
[1] [2, 3] [4]
[1, 4] [2, 3]
[1] [2, 3, 4]
[1, 2] [3] [4]
[1, 2, 4] [3]
[1, 2] [3, 4]
[1, 2, 3] [4]
[1, 2, 3, 4]