4

Questions: Can someone help me to figure out how to calculate cycles that have the maximum amount of pairs (three per cycle - see last example)?

This is what I want to do:
-> pair two users every cycle such that
- each user is only paired once with an other user in a given cycle
- each user is only paired once with every other user in all cycles

Real world:
You meet one new person from a list every week (week = cycle).
You never meet the same person again.
Every user is matched to someone else per week

This is my problem:
I'm able to create combinations of users and select pairs of users that never have met. However, sometimes I'm able to only match two pairs in a cycle instead of three. Therefore, I'm searching for a way to create the optimal selections from a list of combinations.

1) I start with 6 users:

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

2) From this list, I create possible combinations:

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

This gives me:

 .   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

or

   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) Now, I would like to select pairs from this list, such that a user (A to F) is only present once & all users are paired with someone in this cycle

Example:

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

Next cycle, I want to find an other set of three pairs.

I calculated that with 6 users there should be 5 cycles with 3 pairs each:

Example:

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

Can someone help me to figure out how to calculate cycles that have the maximum amount of pairs (three per cycle - see last example)?

4

3 回答 3

3

就像评论中提到的 Whatang 一样，您的问题实际上等同于创建循环式锦标赛的问题。这是 Wikipedia 页面上提到的算法的 Python 版本，另请参阅this和this answer。

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 回答
1

这是一个基于 itertools 的解决方案：

import itertools

def hasNoRepeats(matching):
    flattenedList = list(itertools.chain.from_iterable(matching))
    flattenedSet = set(flattenedList)
    return len(flattenedSet) == len(flattenedList)

def getMatchings(users, groupSize=2):
#   Get all possible pairings of users
    pairings = list(itertools.combinations(users, groupSize))
#   Get all possible groups of pairings of the correct size, then filter to eliminate groups of pairings where a user appears more than once
    possibleMatchings = filter(hasNoRepeats, itertools.combinations(pairings, len(users)/groupSize))
#   Select a series of the possible matchings, making sure no users are paired twice, to create a series of matching cycles.
    cycles = [possibleMatchings.pop(0)]
    for matching in possibleMatchings:
        # pairingsToDate represents a flattened list of all pairs made in cycles so far
        pairingsToDate = list(itertools.chain.from_iterable(cycles))
        # The following checks to make sure there are no pairs in matching (the group of pairs being considered for this cycle) that have occurred in previous cycles (pairingsToDate)
        if not any([pair in pairingsToDate for pair in matching]):
            # Ok, 'matching' contains only pairs that have never occurred so far, so we'll add 'matching' as the next cycle
            cycles.append(matching)
    return cycles

# Demo:

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

matchings = getMatchings(users, groupSize=2)

for matching in matchings:
    print matching

输出：

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

蟒蛇 2.7。这有点蛮力，但它完成了工作。

于 2013-08-11T15:55:59.350 回答
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 xs
removeOccurences(x, xs)remove 每一对xs包含至少一个元素对`x

编辑：停止算法的条件可能需要进一步考虑......

于 2013-08-11T14:39:04.817 回答