4

質問: ペアの最大数 (サイクルごとに 3 つ - 最後の例を参照) を持つサイクルを計算する方法を理解するのを手伝ってくれる人はいますか?

これが私がやりたいことです:
->サイクルごとに2人のユーザーをペアリングします-各ユーザーは
特定のサイクルで他のユーザーと1回だけペアリングされます
-各ユーザーはすべてのサイクルで他のすべてのユーザーと1回だけペアリングされます

現実の世界:
毎週 (週 = サイクル) リストから 1 人の新しい人に会います。
二度と同じ人に会うことはありません。
すべてのユーザーは毎週他の誰かとマッチングされます

これが私の問題
です。ユーザーの組み合わせを作成し、一度も会ったことのないユーザーのペアを選択できます。ただし、サイクルで 3 つではなく 2 つのペアしか一致できない場合があります。したがって、組み合わせのリストから最適な選択を作成する方法を探しています。

1) 6 人のユーザーから始めます。

users = ["A","B","C","D","E","F"]

2) このリストから、可能な組み合わせを作成します。

 x = itertools.combinations(users,2)
    for i in x:
        candidates.append(i)

これは私に与えます：

 .   A,B  A,C  A,D A,E A,F
 .    .   B,C  B,D B,E B,F
 .    .    .   C,D C,E C,F
 .    .    .    .  D,E D,F
 .    .    .    .   .  E,F

また

   candidates = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('A', 'E'), ('A', 'F'), ('B', 'C'), 
       ('B', 'D'), ('B', 'E'), ('B', 'F'), ('C', 'D'), ('C', 'E'), ('C', 'F'), 
       ('D', 'E'), ('D', 'F'), ('E', 'F')]

3) ここで、ユーザー (A から F) が一度だけ存在し、すべてのユーザーがこのサイクルの誰かとペアになるように、このリストからペアを選択したいと思います。

例：

cycle1 = ('A','B'),('C','D') ('E','F')

次のサイクルでは、別の 3 組のペアを見つけたいと思います。

私は、6 人のユーザーの場合、それぞれ 3 つのペアで 5 つのサイクルが必要であると計算しました。

例：

cycle 1: AF BC DE
cycle 2: AB CD EF
cycle 3: AC BE DF
cycle 4: AE BD CF
cycle 5: AD BF CE

最大数のペア (サイクルごとに 3 つ - 最後の例を参照) を持つサイクルを計算する方法を理解するのを手伝ってくれる人はいますか?

4

3 に答える 3

3

コメントでWhatangが述べたように、あなたの問題は実際にはラウンドロビンスタイルのトーナメントを作成することと同等です。これは、ウィキペディアのページに記載されているアルゴリズムの Python バージョンです。これとこの回答も参照してください。

def schedule(users):
    # first make copy or convert to list with length `n`
    users = list(users)  
    n = len(users)

    # add dummy for uneven number of participants
    if n % 2:  
        users.append('_')
        n += 1

    cycles = []
    for _ in range(n-1):
        # "folding", `//` for integer division
        c = zip(users[:n//2], reversed(users[n//2:]))
        cycles.append(list(c))

        # rotate, fixing user 0 in place
        users.insert(1, users.pop())
    return cycles

schedule(['A', 'B', 'C', 'D', 'E', 'F'])

あなたの例では、次のものが生成されます。

[[('A', 'F'), ('B', 'E'), ('C', 'D')],
 [('A', 'E'), ('F', 'D'), ('B', 'C')],
 [('A', 'D'), ('E', 'C'), ('F', 'B')],
 [('A', 'C'), ('D', 'B'), ('E', 'F')],
 [('A', 'B'), ('C', 'F'), ('D', 'E')]]
于 2013-08-11T21:38:52.460 に答える
0

これは疑似コードですが、うまくいくはずです

while length(candidates) > length(users)/2 do
{
    (pairs, candidates) = selectPairs(candidates, candidates)
    if(length(pairs) == length(users)/2)
        cycles.append(pairs)
}

selectPairs(ccand, cand)
{
    if notEmpty(ccand) then
        cpair = cand[0]
        ncand = remove(cpair, cand)
        nccand = removeOccurences(cpair, ncand)
        (pairs, tmp) = selectPairs(nccand, ncand)
        return (pairs.append(cpair), tmp)
    else
        return ([],cand)
}

ここで:
remove(x, xs)remove xfrom remove ペアの要素を少なくとも 1 つ含むxs
removeOccurences(x, xs)のすべてのペア `xxs

EDIT：アルゴリズムを停止する条件は、さらに検討する必要があるかもしれません...

于 2013-08-11T14:39:04.817 に答える