The optimal strategy for choosing pairs from a list of combinations

Question

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

This is what I want to do:
-> a pair of two users each cycle to
- each user connects only once with another user in this cycle
- each user connects only once with every other user in all cycles

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

That's my problem:
I can create user combinations and select pairs of users who have never met. However, sometimes I manage to match only two pairs in a loop instead of three. Therefore, I am looking for a way to create the best choice 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,BA,CA,DA,EA,F . . B,CB,DB,EB,F . . . C,DC,EC,F . . . . D,ED,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, so that the user (from A to F) is present only once, and all users connect to someone in this cycle

Example:

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

The next cycle, I want to find another set of three pairs.

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

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 figure out how to calculate loops with the maximum number of pairs (three per loop - see the last example)?

Answer 1

Here itertools solution is used:

 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 

exit:

 (('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 rough-strong, but he does his job.

Answer 2

Like Whatang mentioned in the comments, your problem is actually equivalent to creating a round robin tournament . This is the version of the Python 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']) 

In your example, this leads to 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 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 xs pair containing at least one element of the `x pair

EDIT: condition for stopping the algorithm may require further thought ...