如何将列表按所有可能的方式分成对

Question

我有一个列表（为了简单起见，假设有6个元素）

L = [0, 1, 2, 3, 4, 5]

我想把它分成成对的组合，且要考虑所有可能的方式。我展示了一些组合：

[(0, 1), (2, 3), (4, 5)]
[(0, 1), (2, 4), (3, 5)]
[(0, 1), (2, 5), (3, 4)]

等等。在这里，(a, b) = (b, a)，也就是说，成对的顺序并不重要，也就是

[(0, 1), (2, 3), (4, 5)] = [(0, 1), (4, 5), (2, 3)]

这样的组合总数是 1*3*5*...*(N-1)，其中 N 是我列表的长度。

我该如何在Python中写一个生成器，来给我所有可能的组合，适用于任意的 N 呢？

Answer 1

这样怎么样：

items = ["me", "you", "him"]
[(items[i],items[j]) for i in range(len(items)) for j in range(i+1, len(items))]

[('me', 'you'), ('me', 'him'), ('you', 'him')]

或者

items = [1, 2, 3, 5, 6]
[(items[i],items[j]) for i in range(len(items)) for j in range(i+1, len(items))]

[(1, 2), (1, 3), (1, 5), (1, 6), (2, 3), (2, 5), (2, 6), (3, 5), (3, 6), (5, 6)]

Answer 2

我觉得标准库里没有一个函数能完全满足你的需求。用 itertools.combinations 可以得到所有可能的单独配对，但这并不能解决所有有效配对组合的问题。

你可以很简单地用以下代码来解决这个问题：

import itertools
def all_pairs(lst):
    for p in itertools.permutations(lst):
        i = iter(p)
        yield zip(i,i)

不过这样做会出现重复，因为它把 (a,b) 和 (b,a) 当作不同的配对，而且还会给出配对的所有排列方式。最后我发现，自己从头写这个代码比试图过滤结果要简单，所以这里是正确的函数。

def all_pairs(lst):
    if len(lst) < 2:
        yield []
        return
    if len(lst) % 2 == 1:
        # Handle odd length list
        for i in range(len(lst)):
            for result in all_pairs(lst[:i] + lst[i+1:]):
                yield result
    else:
        a = lst[0]
        for i in range(1,len(lst)):
            pair = (a,lst[i])
            for rest in all_pairs(lst[1:i]+lst[i+1:]):
                yield [pair] + rest

这个函数是递归的，所以如果列表很长可能会出现栈溢出的问题，但除此之外，它能满足你的需求。

>>> for x in all_pairs([0,1,2,3,4,5]):
    print x

[(0, 1), (2, 3), (4, 5)]
[(0, 1), (2, 4), (3, 5)]
[(0, 1), (2, 5), (3, 4)]
[(0, 2), (1, 3), (4, 5)]
[(0, 2), (1, 4), (3, 5)]
[(0, 2), (1, 5), (3, 4)]
[(0, 3), (1, 2), (4, 5)]
[(0, 3), (1, 4), (2, 5)]
[(0, 3), (1, 5), (2, 4)]
[(0, 4), (1, 2), (3, 5)]
[(0, 4), (1, 3), (2, 5)]
[(0, 4), (1, 5), (2, 3)]
[(0, 5), (1, 2), (3, 4)]
[(0, 5), (1, 3), (2, 4)]
[(0, 5), (1, 4), (2, 3)]

Answer 3

看看这个链接：itertools.combinations，这里面介绍了一个叫做`itertools.combinations`的东西。

>>> import itertools
>>> list(itertools.combinations(range(6), 2))
[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]