How to tackle randomly distributing into pods w/o...

EdFred

Taxi to Parking
Joined
Feb 25, 2005
Messages
30,124
Location
Michigan
Display Name

Display name:
White Chocolate
...running out of valid available spaces.

How would you tackle this?

So I've been tasked with running "brackets" in an upcoming bowling tournament. Each bracket is a pod which is a single elimination tournament that has 8 entrants in it and advancing in the bracket is based on their 3 game scores. A bowler may enter as many brackets as they like. A bowler will only be entered into a single bracket once (i.e. he/she can't bowl against him/herself inside a bracket)

These numbers are just for testing right now as the actual numbers will change.

I have 50 bowlers and each one may enter between 1 and 8 brackets.
I have 233 total entries - which breaks down to 30 brackets with 7 "bye" slots. (233 mod 8)
Here's how I've tested assigning without having to tweak in manually:


Start with first bowler
Pick random number 1 - 30 (bracketID)
if n < 8 and bowlerID isn't present in that bracketID
assign to bracket
else
repick random 1-30 and try again
do this for the number of entries each bowler has

So this works - almost - until I get to the end.
My last bowler has 8 entries, but by the time the code gets there there are only 5 brackets with available spaces - although multiple spaces in each bracket - but you can't have duplicate entries.

What method would you use to fill these pods? - also keep in mind that I don't want duplicate pods where all the bowlers are the same in multiple pods. (i.e. bowlers 1-8 are all in pods 1,2,3,4)
 
Last edited:
tldr

I took a bowling "class" in college. there used to be this bowling alley in jersey when I was growing up that served the best grilled cheese evaarrrrrr. paired well with a nice budweiser.
 
I'm sorry Ed, but I'm afraid I can't do that.

discovery%20doors%20open.jpg
 
I don't know what a "bye" slot is, but you have 233 marbles of 50 different colors, and you want to make 30 bags of 8 marbles, such that each bag has at most one marble of any color, and no two bags are the same? Are leftover marbles allowed, ie can the bowler with 8 entries only get placed into 7 brackets?

I wouldn't worry about randomizing it, finding any answer efficiently might be hard enough. The solution will probably be recursive. Suspect you'll need some way to order/prune things to avoid going through the entire search space. Maybe order the bowlers by the number of entries or something like that.

I'd start with Combinatorial Generation by Frank Ruskey, the pdf is free online. Or Knuth.

Also, up yours for nerd sniping me :)
 
Tto keep the numbers small say I have 15 entries. I have a total of 16 slots to fill. The bye slot means one of those bowlers gets a free pass to round two.

if you have 8 entries, you have to be in 8 different brackets - no competing against yourself.

So what I did was place the bowlers in descending order by the number of entries. Then assign the first bowler randomly to pods. Do the same and move down the list. At first I limited the pod size to 7 and then filling them out to 8 until all entries are accounted for. I've test run with with 50 bowlers and between 4 and 36 entries each, and it seems to work so far.

Also with your 233 example, I can't have less than 7 people in a pod, so I have to take and add another pod getting me to 30. 7 with 7 and 23 with 8.
 
Last edited:
Back
Top