Results 1 to 2 of 2

Math Help - Bridge Group Schedule

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    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.
    Appreciate your help.
    UVAGrad77.

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Sep 2010
    Posts
    1
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: July 27th 2011, 04:18 PM
  2. Repayment schedule
    Posted in the Business Math Forum
    Replies: 3
    Last Post: June 17th 2010, 12:03 PM
  3. cost schedule
    Posted in the Business Math Forum
    Replies: 0
    Last Post: February 6th 2010, 05:36 PM
  4. Bridge Probability
    Posted in the Statistics Forum
    Replies: 3
    Last Post: January 31st 2009, 07:48 AM
  5. [SOLVED] man on bridge
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 16th 2005, 09:37 AM

Search Tags


/mathhelpforum @mathhelpforum