生成所有唯一的對排列

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里斯是正確的 - 我完全沒有意識到，我試圖解決循環問題。我還有一個額外的限制，那就是我正在做的是將人們分組編程練習。因此，如果我有一個奇數的人，我需要創建一個三人組，每個練習包括一個奇怪的人。我目前的想法是（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]]] 

Answer 2

將列表傳遞給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)]) 

從你的描述，你希望每個range(9)以上的2元組的排列應該給你所有的各種排列的，根據你的代碼。但是，這是非常低效的。

但是您還可以通過做簡化代碼如下：

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

Answer 3

正如MatthieuW說，在this answer，它看起來好像你正試圖生成一個round-robin tournament時間表。這可以使用this algorithm輕鬆生成，主要困難是處理奇數球隊（當每個球隊在一輪中獲勝時）。

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