9

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

import itertools

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

可能なすべての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）を1回だけ（フィルタリングされたすべての順列全体で）、（8,5）を1回だけ、（0,1）を1回だけ、（4,7）を表示するようにするにはどうすればよいですか？ ）一度だけなど？

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

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

更新：GarethReesは正しいです-ラウンドロビン問題を解決しようとしていることに完全に気づいていませんでした。私がしているのはペアプログラミング演習のために人々をグループ化することであるという追加の制約があります。したがって、人数が奇数の場合は、3人のグループを作成して、各エクササイズに奇数人を含める必要があります。私の現在の考えは、（1）見えない人を加えることで偶数人にすることです。次に、ペアリング後、見えない人とペアになっている人を見つけ、それらを既存のグループにランダムに配置して、3人のチームを形成します。ただし、これをより適切に行うラウンドロビンのアルゴリズムや調整はまだないのではないかと思います。

更新2：Theodrosのソリューションは、上記で説明した上品な煩わしさなしに、正確に正しい結果を生成します。誰もが驚くほど役に立ちました。

4

3 に答える 3

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

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

更新された質問を説明するために更新します。

3人のグループの不均一なケースを許可するには、次のように変更する必要があります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 に答える
7

リストをに渡して、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)])

説明から、上記の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 に答える
3

MatthieuWがこの回答で述べているように、ラウンドロビントーナメントのスケジュールを作成しようとしているように見えます。これは、このアルゴリズムを使用して簡単に生成できます。主な問題は、奇数のチームを処理することです（各チームが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)]]
于 2013-01-05T12:23:18.370 に答える