This is ridiculous! I have spent a good 8-10 hours from Christmas to the present trying to solve my grandmother Omie's bridge problem. I've even written a schnazzy algorithm to do it using Matlab, but it's going to be crunching all night and I'm not convinced I'll arrive at a solution that meets the criteria. I'm thus opening it up to whoever else deems him/herself worthy or bored enough to solve it:
There are 28 bridge teams that meet in groups of 4 (at 7 houses) over a span of 8 meetings. There seems to be an uproar in New Braunfels, TX, because too many teams keep playing teams they have already played. The goal is to set up a schedule such that each team has minimal repeats.
Sounds easy, right? It's not. Say team 1 plays teams 2, 3, and 4 at the first meeting. Then you have teams 5-28 to work with for the remaining 7 meetings. But team 2 now can't play team 3 or 4 ever again, in an ideal world. I've gotten to the point where I have around 300 schedules that work so that the average team plays only 6 other teams twice (and no team repeats more than once). Now I'm optimizing those schedules by rearranging the meetings (random permutations) so that none of the repeated teams play in consecutive meetings. I don't think it's possible to avoid repeats at all - a mean of 5.3 teams is the lowest I could routinely get after thousands of random trials.
If you have Matlab and you want my code, email me. :) I would love some help!
Subscribe to:
Post Comments (Atom)
6 comments:
help me understand: team A plays 8 events, 3 teams at each event, 24 teams total out of 27, correct?
Yes, that's correct. It's not that team A should play all the teams, but just to have the fewest number of repeats (as far apart from each other in the schedule as possible).
This morning I got one optimized schedule where only 10 teams have a back-to-back repeat with one other team, and where the max number of teams a team could repeat with is 7.
"If you have Matlab and you want my code, email me"??? The :) at the end of that statement does not redeem its extreme geekiness.
Wow. And my husband jumped on it, of course.
Riddle me this: can your Matlab (of what do you speak?) ensure a good hand for me in all future games of bridge? Or even just most? I'd take that, please. Thonk yew.
since no team can play them all, it seems likely that each team can minimize repeats. see here for a 28-team schedule with no repeats. of course, that schedule assumes all teams play at the same location. i think the key is getting your omie to get her group to meet in larger clusters a few times. otherwise they'll have to settle for seeing the same old, cranky women week after week.
Ooohh.. I like it. Breathrough innovation from Micah. You don't want 28 women playing bridge in a single house in South Texas during the summer. Remember the Alamo. Need I say more.
Yeah, I think you're right, Micah. I'd like to understand how to figure this out theoretically. I think I'd stake at least a toad's life to bet there's no way to ensure that 0 teams play another team back-to-back. I'm getting a 1:1000 success rate for a schedules where the max number of teams a team could repeat with is 7. No successful ones for 6 yet, but I only started that run this afternoon.
Post a Comment