生成所有唯一的对置换

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了标准库中的-data结构：

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

它将对象（此处为int）放入双端队列。然后旋转并构建从两端到中间的连续对。可以想象这是将中间的双端队列折叠回去。明确说明：

大小写不均元素 ：

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