|No such thing as a small change
rchiav's scratchpadby rchiav (Deacon)
|on Jun 01, 2004 at 14:49 UTC
Here's the issue I've run into with an app I'm making:
The program will manage what is called "Brackets" for bowling tournaments or leagues. The structure is pretty simple. Each bracket consists of 8 slots for individuals. The people are (somewhat) randomly assigned to a slot in the bracket. These slots are broken into 4 pairs, with the first and second slot being one pair, the third and fourth being another, etc.
Now these pairs of people don't necicairly bowl on the same pair of lanes but they are bowling against one another for the purposes of the brackets. The way they compete is that they bowl the league or tournament as normal, but they use the score of their first game to determine the winner of the first round. Then those who have survived the first round use their score from the second game to determine the winner of the secound round. And for the two people who made it to the third round, they will use the score from their third game to determine the winner. The graphical representation is below..
Now none of this is difficult to figure out. Where it becomes tricky is when there are multiple brackets. The way it works is that anyone wishing to participate pays $5 for each bracket they want to get in. There's no hard limit as to the number that people can enter. Larger tournaments have had over 150 brackets. The only restriction on multiple entries is that you can only be in each bracket once. If you say you want to be in 10, and it turns out that there's only enough people for 6, you're refunded the difference.
Now, on to the problem:
What I'm trying to do is develop a system that will eliminate all duplicate 1st round pairings when possible. This means that if it's statistically possible, two people will not bowl each other more than once in the first round. I've dabbled with this for months and I just can't get my arms around it. Here's my logic up to this point.
Programatically speaking, I thought the first step would be to determine if it's statistically possible. This proved much harder than I anticipated. That might have more to do with my ignorance of statistics than the actual difficulty of the problem though.
What I know:
With this, I figured that The number of pairings I need is going to be num_brackets * 4. But unfortunately, I can't calculate the possible pairings as a simple permutation. For some, the reason might be obvious, but for others, the reason is that not all entrants will be available for all pairings. Simply put, If someone enters twice, once they have been paired up twice, their remaing potential parings are no longer valid. I'm not sure how to caluclate this with the added dimention.
Based on the last requirement above, I decided to tackle it from a different direction. What I thought about doing is making a data structure that would have each person along with the number of brackets they were in, and the opponents they have already been set against. Then build the pairings to build the bracket, excluding any opponent they have already been set against. The problem with this is that if I can't find an opponent that they haven't been set against, it really doesn't mean that some other combination wouldn't work.
The last thing that's been running around my brain is that I should create a distribution between brackets (or buckets) that would give me the best chance to accomplish this. But again, I'm at a loss on how to do this properly.
You know that funny face babies make when someone pushes on their soft spot? That's what I look like about now. If anyone has any insight on how I should tackle this, I'd greatly appreciate it. Either message me and I'll send you my email address or scratchpad it and let me know.
PS - There's always brute force, but I'm trying to avoid that.