生成所有唯一的对置换 [英] Generating all unique pair permutations

问题描述

我需要生成所有可能的配对，但受限于特定配对仅在结果中出现一次。因此例如：

I need to generate all possible pairings, but with the constraint that a particular pairing only occurs once in the results. So for example:

import itertools

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

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

generates all possible two-paired permutations; here's a small subset of the output:

...
[(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）仅一次，等等。

How do I further filter it so that I only ever see (8,4) once (throughout all of the filtered permutations), and (8,5) only once, and (0,1) only once, and (4,7) only once, etc.?

我希望排列使得每个两个元素的配对仅发生一次。

Basically I want the permutations such that each two-element pairing happens only once.

我敢打赌，还有一个解决问题的附加itertool

I'll bet there's an additional itertool that would solve this but I'm not expert enough to know what it is.

更新：Gareth Rees是正确的-我完全不知道这是什么。我正在尝试解决循环问题。我还有一个限制，那就是我要做的是将人员分组以进行配对编程练习。因此，如果我的人数为奇数，则需要创建一个三人一组，以便每次练习都包括一个奇数的人。我目前的想法是（1）通过增加一个看不见的人来使人数相等。然后，在配对之后，找到与看不见的人配对的人，并将他们随机放入一个现有的组中，组成一个三人一组。但是，我想知道是否还没有一种算法或轮循机制的调整可以更好地做到这一点。

Update: Gareth Rees is correct -- I was completely unaware that I was trying to solve the round-robin problem. I have an additional constraint which is that what I'm doing is grouping people for pair-programming exercises. Thus, if I have an odd number of people, I need to create a group of three to include an odd person for each exercise. My current thinking is to (1) make an even number of people by adding in an invisible person. Then, after the pairing, find the person paired with the invisible person and randomly place them into an existing group to form a team of three. However, I wonder if there isn't already an algorithm or adjustment to round-robin that does this in a better way.

更新2 ：Theodros的解决方案可以产生正确的结果，而不会引起我上面描述的麻烦。

Update 2: Theodros' solution produces exactly the right result without the inelegant futzing about I describe above. Everyone's been amazingly helpful.

推荐答案

我想分享一种使用 deque -标准库中的数据结构：

I'd like to share a different implementation of round-robin scheduling that makes use of the deque-data structure from the Standard Library:

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

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

It puts the objects(ints here) in the deque. Then it rotates and builds consecutive pairs taking from both ends towards the middle. One can imagine this as folding the deque in the middle back on itself. To make it clear:

元素不均匀的情况：

 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 始终保持在左上角。

In case of even elements an additional step is required.
(I missed the first time cause I only checked the uneven case. This yielded a horribly wrong algorithm... which shows me how important it is to check edge cases when implementing an algorithm...)
This special step is that I swap the two leftmost elements (which are the first and last elements of the deque) before each rotation -- this means the 0 stays all the time upper left.

大小写为偶数

 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的可读性较低：

What haunts me about this version is the amount of code duplication, but I couldn't find a way to improve while keeping it as readable. Here's my first implementation, which is less readable 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）：

To allow in the uneven case for groups of three you just need to change 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]]]

这篇关于生成所有唯一的对置换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！