# Math Help - Bridge Group Schedule

1. ## 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.

2. Here's a Python program which should find a solution if one exists, using a brute-force approach. However, it may not be very helpful. There are (5775 8) = 3 x 10^25 potential solutions; if we evaluate a million per second, it will take almost a trillion years to get through them all.

Code:
# 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