4

我需要一个 of 函数，它可以将一个序列分成对，然后将它们组合起来，使组合中的所有元素都是唯一的。我已经尝试了许多使用 python 的 itertools 的方法，但还没有找到解决方案。

为了说明我想要一个可以采用这个序列的函数： [1, 2, 3, 4]

并将其拆分为以下3种组合：

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

它也应该适用于更长的序列，但不必处理奇数长度的序列。例如。

[1,2,3,4,5,6]

分成以下15种组合：

[[1, 2], [3, 4], [5, 6]]
[[1, 2], [3, 5], [4, 6]]
[[1, 2], [3, 6], [4, 5]]
[[1, 3], [2, 4], [5, 6]]
[[1, 3], [2, 5], [4, 6]]
[[1, 3], [2, 6], [4, 5]]
[[1, 4], [2, 3], [5, 6]]
[[1, 4], [2, 5], [3, 6]]
[[1, 4], [2, 6], [3, 5]]
[[1, 5], [2, 3], [4, 6]]
[[1, 5], [2, 4], [3, 6]]
[[1, 5], [2, 6], [3, 4]]
[[1, 6], [2, 3], [4, 5]]
[[1, 6], [2, 4], [3, 5]]
[[1, 6], [2, 5], [3, 4]]

... 等等。

名为 Maple 的 CAS 在名称setpartition下实现了此功能。

编辑：修复了 wks 指出的一个严重的深夜打字错误，并澄清了输出。

4

3 回答 3

5

itertools确实是你的朋友：

from itertools import permutations

def group(iterable, n=2):
    return zip(*([iter(iterable)] * n))

for each in permutations([1, 2, 3, 4, 5, 6]):
    print map(list, group(each))

结果：

[[1, 2], [3, 4], [5, 6]]
[[1, 2], [3, 4], [6, 5]]
[[1, 2], [3, 5], [4, 6]]
[[1, 2], [3, 5], [6, 4]]
[[1, 2], [3, 6], [4, 5]]
[[1, 2], [3, 6], [5, 4]]
[[1, 2], [4, 3], [5, 6]]
[[1, 2], [4, 3], [6, 5]]
[[1, 2], [4, 5], [3, 6]]
...

[编辑] @FrederikNS：在您澄清问题并自己找到答案后，这是我的解决方案：

from itertools import combinations

def setpartition(iterable, n=2):
    iterable = list(iterable)
    partitions = combinations(combinations(iterable, r=n), r=len(iterable) / n)
    for partition in partitions:
        seen = set()
        for group in partition:
            if seen.intersection(group):
                break
            seen.update(group)
        else:
            yield partition

for each in setpartition([1, 2, 3, 4]):
    print each
print
for each in setpartition([1, 2, 3, 4, 5, 6]):
    print each

结果：

((1, 2), (3, 4))
((1, 3), (2, 4))
((1, 4), (2, 3))

((1, 2), (3, 4), (5, 6))
((1, 2), (3, 5), (4, 6))
((1, 2), (3, 6), (4, 5))
((1, 3), (2, 4), (5, 6))
((1, 3), (2, 5), (4, 6))
((1, 3), (2, 6), (4, 5))
((1, 4), (2, 3), (5, 6))
((1, 4), (2, 5), (3, 6))
((1, 4), (2, 6), (3, 5))
((1, 5), (2, 3), (4, 6))
((1, 5), (2, 4), (3, 6))
((1, 5), (2, 6), (3, 4))
((1, 6), (2, 3), (4, 5))
((1, 6), (2, 4), (3, 5))
((1, 6), (2, 5), (3, 4))
于 2012-05-12T23:50:01.587 回答
1

我终于自己搞定了（pillmuncher 的回答确实让我朝着正确的方向轻推，组功能完全是他的）：

def group(iterable, n=2):
    return zip(*([iter(iterable)] * n))

def set_partition(iterable, n=2):
    set_partitions = set()

    for permutation in itertools.permutations(iterable):
        grouped = group(list(permutation), n)
        sorted_group = tuple(sorted([tuple(sorted(partition)) for partition in grouped]))
        set_partitions.add(sorted_group)

    return set_partitions

partitions = set_partition([1,2,3,4], 2)
for part in partitions:
    print(part)

这打印：

((1, 4), (2, 3))
((1, 3), (2, 4))
((1, 2), (3, 4))
于 2012-05-13T09:54:51.987 回答
-1

试试这个：

def function(list):
    combinations = []
    for i in list:
        for i2 in list:
            if not [i2, i] in combinations:
                 combinations.append([i, i2])
    return combinations

这将返回所有可能的组合。

希望这可以帮助！

于 2012-05-12T23:47:34.890 回答