# Bridge Group Schedule

• Mar 10th 2010, 11:30 AM
Bridge Group Schedule
A Practical Combinatorics Problem: Neighborhood Bridge Group Schedule
Our neighborhood bridge group has 12 pairs. We play during an 8-month season from October to May. Three pairs host each month; each host invites 3 pairs, so all12 pairs play each month. So, over 8 months each pair will host twice randomly. We want to create a seasonal schedule that:
· Guarantees each pair will socialize with every other pair (i.e., no pair will be excluded from meeting any of the other 11 pairs), and
· Guarantees every pair will play with every other pair twice, but not more than three times.
Please create a program or generating funcrtion that can be run to create such a schedule using pair numbers 1 through 12.
```# Restated: There are (m*n)!/(m!)^n*n! ways to divide m*n items into n groups # of m each.  For m = 4 and n = 3, this yields 5775 possible groupings. # Find a set of 8 groupings such that, for any two items i and j, i and j are # in the same group at least twice and not more than 3 times. MAX_COUNT = 3 MIN_COUNT = 2 def permute(aset):     """Generator to return all permutations of a set."""     if len(aset) == 0:         yield None     elif len(aset) == 1:         yield list(aset)     else:         for x in aset:             for p in permute(aset - set([x])):                 yield [x] + p def choose(alist, n):     """Generator to return all combinations of n items from a list."""     if len(alist) == n:         yield list(alist)     elif len(alist) < n or n <= 0:         yield []     elif n == 1:         for x in alist:             yield [x]     else:         for i in xrange(len(alist) - n + 1):             for c in choose(alist[i + 1:], n - 1):                 yield [alist[i]] + c def find_groupings(m, n):     for permutation in permute(set(xrange(1, m*n + 1))):         grouping = []         for i in xrange(n):             grouping.append(frozenset(permutation[i*m : (i + 1)*m]))         grouping = frozenset(grouping)         yield grouping def is_solution(groupings, m, n):     pair_count = {}     for grouping in groupings:         for group in grouping:             for pair in choose(list(group), 2):                 tpair = tuple(pair)                 count = pair_count.get(tpair, 0)                 if count > MAX_COUNT:                     return False                 pair_count[tpair] = count + 1     for pair in choose(list(xrange(1, m*n + 1)), 2):         if pair_count.get(tuple(pair), 0) < MIN_COUNT:             return False     return True def solve(m, n, k):     groupings = set(find_groupings(m, n))     for x in choose(list(groupings), k):         if is_solution(x, m, n):             return x     return None                     for x in solve(4, 3, 8):     print x```