Optimal strategy for choosing pairs from a list of combinations

Question

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

Answer 1

Like Whatang mentioned in the comments your problem is in fact equivalent to that of creating a round-robin style tournament. This is a Python version of the algorithm mentioned on the Wikipedia page, see also this and 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'])

For your example it produces the following:

[[('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')]]

Answer 2

Here's an itertools-based solution:

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

output:

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

Python 2.7. It's a little brute-forcey, but it gets the job done.

Answer 3

Ok this is pseudo code, but it should do the trick

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

where:
remove(x, xs) remove x from xs
removeOccurences(x, xs) remove every pair of xs containing at least one element of the pair `x

EDIT: the condition to stop the algorithm may need further thought ...