0

不知道如何在标题中解释问题。

这是问题所在：

假设我们有 4 组：

(a, b, c, d)
(e, f)
(g, h, i)
(j, k, l, m, n)

现在给了我一个 4 元素元组，例如(a, e, h, m)，两个都不是来自一个组，所以我返回 True。如果给定(a, b, e, g)，则a, b来自一组，返回 False。

然后这是我目前的想法，我给每个元素一个以组号开头的 id 并测试是否重复。

g1 = ['1a', '1b', '1c', '1d']
g2 = ['2e', '2f']
g3 = ['3g', '3h', '3i']
g4 = ['4j', '4k', '4l', '4m', '4n']


def test(elements):
    if len(elements) != 4:
        return False

    stack = []
    for e in elements:
        mark = e[:1]
        if mark in stack:
            return False
        stack.append(mark)

    ga = set(g1 + g2 + g3 + g4)
    return set(elements).issubset(ga)


print test(('1a', '1b', '2e', '3g'))
print test(('1a', '2e', '3g', '4m'))

但我认为字符串比较不是一个非常优雅的解决方案，这可以通过另一种更快的算法来完成吗？

4

2 回答 2

4

如果所有元素都是可散列的，我会使用set.intersection：

g1 = set(['1a', '1b', '1c', '1d'])
g2 = set(['2e', '2f'])
g3 = set(['3g', '3h', '3i'])
g4 = set(['4j', '4k', '4l', '4m', '4n'])

sets = [g1,g2,g3,g4]
test_this = ['1a','2e','3g','4j']

all(len(s.intersection(test_this)) <= 1 for s in sets)

或者，如果您不想更改 g1,g2 的类型 ...您可以更改的类型test_this：

g1 = ['1a', '1b', '1c', '1d']
g2 = ['2e', '2f']
g3 = ['3g', '3h', '3i']
g4 = ['4j', '4k', '4l', '4m', '4n']
lists = [g1,g2,g3,g4]
test_this = set(['1a','2e','3g','4j'])

all( len(test_this.intersection(lst)) <= 1 for lst in lists )

这里的美妙之处在于它all足够聪明，可以短路——而且由于我们使用的是生成器表达式，我们不需要预先计算所有的交点。只要所有先前的交叉点的长度小于或等于 1，Python 只会继续计算交叉点。

于 2012-11-15T05:33:09.877 回答
2

只是在解释器中玩耍，与 mgilson 相同，但您不需要检查len()，现有的 set() 评估为 True。

>>> g1 = ['1a', '1b', '1c', '1d']
>>> g2 = ['2e', '2f']
>>> g3 = ['3g', '3h', '3i']
>>> g4 = ['4j', '4k', '4l', '4m', '4n']
>>>
>>> groups = (g1, g2, g3, g4)
>>> t1 = ('1a', '1b', '2e', '3g')
>>> t2 = ('1a', '2e', '3g', '4m')
>>>
>>> all(set(t2).intersection(g) for g in groups)
True
>>> all(set(t1).intersection(g) for g in groups)
False
>>>
于 2012-11-15T05:38:42.327 回答