すべてのユニークなペア順列を生​​成する

Question

可能なすべてのペアリングを生成する必要がありますが、特定のペアリングが結果内で1回だけ発生するという制約があります。したがって、たとえば：

import itertools 

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

はすべての可能な2ペアの順列を生成します。一度だけ、私が今までに一度だけ（フィルタリング順列の全てを通して）（8,4）を参照するように、私はさらにそれをフィルタリングするにはどうすればよい

... 
[(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,5）：ここでは、小さな出力のサブセットです、（0,1）は1回だけ、（4,7）は1回だけなどです。

基本的に、各2要素ペアリングが1回だけ起こるような順列が必要です。

これを解決する追加のitertoolがあると思いますが、私はそれが何であるかを知るには十分な専門家ではありません。

更新：Gareth Reesが正しい - 私はラウンドロビン問題を解決しようとしていたことを完全に知らなかった。私にはもう一つの制約があります。私がやっているのは、ペアプログラミングの演習のために人々をグループ化することです。したがって、奇数の人がいる場合は、3つのグループを作成して、それぞれの練習に奇妙な人物を含める必要があります。私の現在の考えは、（1）目に見えない人を加えて偶数人を作ることです。その後、ペアリングした後、目に見えない人とペアを組んだ人を見つけ、既存のグループにランダムに配置して3人のチームを形成します。しかし、これをより良い方法で行うラウンドロビンのアルゴリズムや調整がまだないのではないかと思います。

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

オブジェクト（ここでは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 

追加のステップが必要とされていても要素の場合には。
（私は不揃いのケースのみをチェックしたため、初めてのことは忘れましたが...これはひどく間違ったアルゴリズムをもたらしました...アルゴリズムを実装する際にエッジケースをチェックすることがどれほど重要かを示しています...）
この特別なステップは各回転の前に、左端の2つの要素（デキューの最初と最後の要素）を入れ替えます。これは、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)を変更する必要が3のグループのために不均一な場合に許可するには：

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に渡すと、各タプルが1回だけ存在することが確認されます。あなたの説明から

>>> 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を使用して生成することができます。主な難点は、奇数のチームの処理（各チームが1つのラウンドでバイを獲得するとき）です。例えば

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

、9つのチームと：

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