python - 生成所有唯一对排列

Question

我需要生成所有可能的配对，但有一个特定配对在结果中只出现一次的限制。例如:

import itertools

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

生成所有可能的双对排列；这是输出的一小部分:

...
[(8, 4), (7, 6), (5, 3), (0, 2)]
[(8, 4), (7, 6), (5, 3), (1, 0)]
[(8, 4), (7, 6), (5, 3), (1, 2)]
[(8, 4), (7, 6), (5, 3), (2, 0)]
[(8, 4), (7, 6), (5, 3), (2, 1)]
[(8, 5), (0, 1), (2, 3), (4, 6)]
[(8, 5), (0, 1), (2, 3), (4, 7)]
[(8, 5), (0, 1), (2, 3), (6, 4)]
[(8, 5), (0, 1), (2, 3), (6, 7)]
[(8, 5), (0, 1), (2, 3), (7, 4)]
[(8, 5), (0, 1), (2, 3), (7, 6)]
[(8, 5), (0, 1), (2, 4), (3, 6)]
[(8, 5), (0, 1), (2, 4), (3, 7)]
[(8, 5), (0, 1), (2, 4), (6, 3)]
...

如何进一步过滤它，以便我只看到 (8,4) 一次(在所有过滤后的排列中)，并且 (8,5) 仅一次，并且 (0,1) 仅一次，并且 ( 4,7) 只有一次，等等？

基本上我想要的排列使得每个双元素配对只发生一次。

我敢打赌还有一个额外的 itertool 可以解决这个问题，但我不够专业，不知道它是什么。

更新:Gareth Rees 是正确的——我完全没有意识到我正在尝试解决循环问题。我还有一个额外的限制，那就是我正在做的是将人们分组进行结对编程练习。因此，如果我有奇数的人，我需要创建一个三人小组，每个练习都包括一个奇数的人。我目前的想法是(1)通过添加一个隐形人来使人数为偶数。然后，配对后，找到与隐身人配对的人，将他们随机分配到一个已有的组中，组成三人一组。但是，我想知道是否还没有一种算法或对循环法的调整可以更好地做到这一点。

更新 2:Theodros 的解决方案产生了完全正确的结果，没有我上面描述的不雅的胡扯。每个人都提供了惊人的帮助。

Answer 1

我想分享一个不同的循环调度实现，它使用标准库中的 deque 数据结构:

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


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


print round_robin(2)
   [[[0, 1]]]

它将对象(此处为整数)放入双端队列中。然后它旋转并构建从两端到中间的连续对。可以将其想象为将中间的双端队列自身折叠起来。说清楚:

大小写不均匀元素:

 round 1     round 2       # pairs are those numbers that sit
----------  ---------      # on top of each other
0 1 2 3 4   8 0 1 2 3
8 7 6 5     7 6 5 4

如果是偶数元素，则需要额外的步骤。
(我错过了第一次，因为我只检查了不均匀的情况。这产生了一个可怕的错误算法......这告诉我在实现算法时检查边缘情况是多么重要......)
这个特殊步骤是我在每次旋转之前交换最左边的两个元素(它们是双端队列的第一个和最后一个元素)——这意味着 0 始终保持在左上角。

大小写偶数元素:

 round 1     round 2       # pairs are those numbers that sit
----------  ---------      # on top of each other
0 1 2 3     0 7 1 2
7 6 5 4     6 5 4 3

这个版本困扰我的是代码重复的数量，但我找不到在保持其可读性的同时进行改进的方法。这是我的第一个实现，IMO 的可读性较差:

def round_robin(n):
    is_even = (n % 2 == 0)
    schedule = []
    d = deque(range(n))
    for i in range(2 * ((n - 1) / 2) + 1):
        schedule.append(
                        [[d[j], d[-j-1]] for j in range(n/2)])
        if is_even:
            d[0], d[-1] = d[-1], d[0]
        d.rotate()
    return schedule

更新以说明更新后的问题:

要允许三人一组的不平衡情况，您只需更改 round_robin_odd(d, n):

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

这给出:

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