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.
Appreciate your help.
UVAGrad77.

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

---