9

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

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 的解决方案产生了完全正确的结果，而没有我上面描述的不雅点。每个人都非常乐于助人。

4

3 回答 3

7

将列表传递给以set确保每个元组仅存在一次。

>>> from itertools import permutations
>>> set( [ zip( perm[::2], perm[1::2] ) for perm in permutations( range( 9 ) ) ] )
set([(7, 3), (4, 7), (1, 3), (4, 8), (5, 6), (2, 8), (8, 0), (3, 2), (2, 1), (6, 2), (1, 6), (5, 1), (3, 7), (2, 5), (8, 5), (0, 3), (5, 8), (4, 0), (1, 2), (3, 8), (3, 1), (6, 7), (2, 0), (8, 1), (7, 6), (3, 0), (6, 3), (1, 5), (7, 2), (3, 6), (0, 4), (8, 6), (3, 5), (4, 1), (6, 4), (5, 4), (2, 6), (8, 2), (2, 7), (7, 1), (4, 5), (8, 3), (1, 4), (6, 0), (7, 5), (2, 3), (0, 7), (8, 7), (4, 2), (1, 0), (0, 8), (6, 5), (4, 6), (0, 1), (5, 3), (7, 0), (6, 8), (3, 4), (6, 1), (5, 7), (5, 2), (0, 2), (7, 4), (0, 6), (1, 8), (4, 3), (1, 7), (0, 5), (5, 0), (7, 8), (2, 4), (8, 4)])

根据您的描述，您希望上面的每个 2 元组排列都range( 9 )应该根据您的代码为您提供所有各种排列。但是，这是非常低效的。

但是，您可以通过执行以下操作进一步简化代码：

>>> list( permutations( range( 9 ), 2 ) )
[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (1, 0), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 0), (2, 1), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (3, 0), (3, 1), (3, 2), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (4, 0), (4, 1), (4, 2), (4, 3), (4, 5), (4, 6), (4, 7), (4, 8), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4), (5, 6), (5, 7), (5, 8), (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 7), (6, 8), (7, 0), (7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 6), (7, 8), (8, 0), (8, 1), (8, 2), (8, 3), (8, 4), (8, 5), (8, 6), (8, 7)]

该方法permutations还接受一个长度参数，允许您指定返回的元组的长度。因此，您使用了正确itertool提供的函数，但错过了元组长度参数。

itertools.permutations 文档

于 2013-01-05T06:00:43.547 回答
7

我想分享一个不同的循环调度实现，它使用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]]]

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

案例不均匀元素：

 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]]]
于 2013-01-05T12:28:07.947 回答
3

正如 MatthieuW 在此答案中所说，您似乎正在尝试为循环锦标赛生成时间表。这可以使用该算法轻松生成，主要困难是处理奇数支球队（当每支球队在一轮中轮空时）。

def round_robin_schedule(n):
    """
    Generate a round-robin tournament schedule for `n` teams.
    """
    m = n + n % 2               # Round up to even number.
    for r in xrange(m - 1):
        def pairing():
            if r < n - 1:
                yield r, n - 1
            for i in xrange(m // 2 - 1):
                p, q = (r + i + 1) % (m - 1), (m + r - i - 2) % (m - 1)
                if p < n - 1 and q < n - 1:
                    yield p, q
        yield list(pairing())

例如，有九个团队：

>>> list(round_robin_schedule(9))
[[(0, 8), (2, 7), (3, 6), (4, 5)],
 [(1, 8), (2, 0), (4, 7), (5, 6)],
 [(2, 8), (3, 1), (4, 0), (6, 7)],
 [(3, 8), (4, 2), (5, 1), (6, 0)],
 [(4, 8), (5, 3), (6, 2), (7, 1)],
 [(5, 8), (6, 4), (7, 3), (0, 1)],
 [(6, 8), (7, 5), (0, 3), (1, 2)],
 [(7, 8), (0, 5), (1, 4), (2, 3)],
 [(0, 7), (1, 6), (2, 5), (3, 4)]]
于 2013-01-05T12:23:18.370 回答