7

我正在寻找一种 Pythonic 方法来(a,b) ≠ (b,a)为包含偶数n项的集合生成所有成对唯一的唯一配对（其中配对是由对组成的系统，并且成对唯一表示）。

我喜欢这里的代码：

for perm in itertools.permutations(range(n)):
    print zip(perm[::2], perm[1::2])

除了它生成所有顺序唯一、成对唯一的配对，或者(n/2)!比我想要的多倍的配对（冗余），虽然我可以过滤掉，但它确实让我的程序陷入了困境n。

也就是说，对于n = 4，我正在寻找以下输出（12 个唯一配对）：

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

请注意(a,b) ≠ (b,a).

这可能吗？我也可以使用为 where 生成 3 个非成对唯一配对的函数，n = 4因为(a,b) = (b,a)从那里置换我需要的内容很简单。我的主要目标是避免配对中对的顺序进行多余的排列。

提前感谢您的帮助和建议——我真的很感激。

4

3 回答 3

3

我认为这为您提供了所需的基本配对：1 when N=2; 3 时N=4；15 时N=6；105 时n=8等。

import sys

def pairings(remainder, partial = None):
    partial = partial or []

    if len(remainder) == 0:
        yield partial

    else:
        for i in xrange(1, len(remainder)):
            pair = [[remainder[0], remainder[i]]]
            r1   = remainder[1:i]
            r2   = remainder[i+1:]
            for p in pairings(r1 + r2, partial + pair):
                yield p

def main():
    n = int(sys.argv[1])
    items = list(range(n))
    for p in pairings(items):
        print p

main()
于 2013-05-13T04:00:23.977 回答
1

在链接的问题“生成所有唯一对排列”（此处）中，给出了一种算法来为任何给定的n生成循环调度。也就是说，n支球队的每组可能的比赛/配对。

所以对于 n = 4（假设是排他的），那将是：

[0, 3], [1, 2]
[0, 2], [3, 1]
[0, 1], [2, 3]

现在我们已经获得了这些分区中的每一个，我们只需要找到它们的排列即可获得完整的配对列表。即[0, 3], [1, 2]是一组四个的成员：[0, 3], [1, 2]（本身）和[3, 0], [1, 2]和[0 , 3], [2, 1]和[3, 0], [2, 1]。

要从一个成员中获取组的所有成员，您需要进行排列，其中每对可以翻转或不翻转（例如，如果它们是 n 元组而不是对，那么每个都有 n! 选项一）。所以因为你有两对和选项，每个分区产生 2 ^ 2 对。所以你总共有 12 个。

执行此操作的代码，其中 round_robin(n) 返回对列表的列表。所以 round_robin(4) --> [[[0, 3], [1, 2]], [[0, 2], [3, 1]], [[0, 1], [2, 3]] ]。

def pairs(n):
    for elem in round_robin(n):
        for first in [elem[0], elem[0][::-1]]:
            for second in [elem[1], elem[1][::-1]]:
                print (first, second)

这种方法产生的比你想要的少，然后上升，而不是产生比你想要的多并摆脱一堆，所以它应该更有效。（[::-1] 是不可变地反转列表的巫术）。

这是另一个帖子中的循环算法（由 Theodros Zelleke 编写）

from collections import deque

def round_robin_even(d, n):
    for i in range(n - 1):
        yield [[d[j], d[-j-1]] for j in range(n/2)]
        d[0], d[-1] = d[-1], d[0]
        d.rotate()

def round_robin_odd(d, n):
    for i in range(n):
        yield [[d[j], d[-j-1]] for j in range(n/2)]
        d.rotate()

def round_robin(n):
    d = deque(range(n))
    if n % 2 == 0:
        return list(round_robin_even(d, n))
    else:
        return list(round_robin_odd(d, n))
于 2013-05-12T21:03:39.603 回答
0

我不确定我是否很好地理解了这个问题，无论如何这是我的解决方案：

import itertools
n = 4
out = set()
for perm in itertools.permutations(range(n)):
    pairs = tuple(sorted(zip(perm[::2], perm[1::2])))
    out.add(pairs)

for i, p in enumerate(sorted(out)):
    print i,p

对于 n=4，它返回 12 个唯一对，对于 n=6，它返回 120 个。

于 2013-05-12T22:40:28.927 回答