生成生成集的算法

Question

鉴于此输入:[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:我知道如何做一个powerset.这是一个简单的实现:

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

Answer 1

这应该工作,虽然我没有足够的测试.

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))

输出:

[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]

Answer 2

那这个呢？我还没有测试过,但我会稍后再试一下......

我认为这种技术称为动态编程:

1. 拿第一个元素[1]
   你能用它创造什么？只要[1]

2. 拿第二个[2]
   现在你有两种可能性:[1,2]和[1] [2]

3. 取第三个[3]
   通过第一号2的[1,2]一个可以创建[1,2,3]和[1,2] [3]
   随着号为2的第二[1] [2]一个可以创建[1,3] [2]和[1] [2,3]和[1] [2] [3]

我希望我试图展示的内容已经足够清楚了.(如果没有,请发表评论!)