生成生成集的算法 [英] Algorithm to generate spanning set

问题描述

给出以下输入：[1,2,3,4]

Given this input: [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生成器函数，但无法获得正确的组合。

Every set has all the elements of the original set, permuted to appear in unique subsets. What is the algorithm that produces these sets? I've tried Python generator functions using choose, permutation, combination, power set, and so on, but can't get the right combination.

2009年1月20日

20 Jan 2009

这不是作业问题。这是我针对www.projecteuler.net问题＃118所做的改进的答案。我已经有了一个较慢的解决方案，但想出了一个更好的方法-除非我不知道如何进行生成设置。

This is not a homework question. This is an improved answer I was working on for www.projecteuler.net problem # 118. I already had a slow solution but came up with a better way -- except I could not figure out how to do the spanning set.

从就职典礼聚会回来时，我会发布代码。

I'll post my code when I get back from an Inauguration Party.

2009年1月21日

21 Jan 2009

这是我最终使用的算法：

This is the eventual algorithm I used:

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：我知道如何进行功率设定。这是一个简单的实现：

@Yuval F: I know how to do a powerset. Here's a straightforward implementation:

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

输出：

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

这篇关于生成生成集的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！