Balls in boxes algorithm

February 9, 2007 1:35 PM

Is there a standard ball picking algorithm? I have 10 balls that I want put in four boxes (A-D). Every box can hold zero to all balls.

So one possible combination is:
box A: 0,1,3
box B: 5
box C: 2,4,6,7,8,9
box D: -

I want to generate all possible combinations. I realise that this makes 4^10, which is over 1 million possibilities so efficiency is important.

I expected that this would be a common homework problem for computer scientists and I assumed there would be a sort-of standard way to do this (like "quicksort" is a standard way to sort). I don't think I know the terms to search for though, because I cannot find anything.

Any help with this specific problem would be appreciated (pseudo code is fine). If there is a language that is exceptionally suited for this kind of task, I would be interested in that as well. If there are useful websites about this problem, that would be great as well.

posted by davar to science & nature (10 comments total)

Every ball can be in A, B, C, D. So what you have is nothing more than a 10 digit base 4 counter. Just go in order:

AAAAAAAAAA
AAAAAAAAAB
etc.
posted by chairface at 1:44 PM on February 9, 2007

Tell me I didn't just do your homework for you.
posted by chairface at 1:46 PM on February 9, 2007

You're doing it the wrong way round. Assign boxes to balls. Binary-wise make each of the boxes A,B,C,D 00, 01,10,11 respectively. Then you can represent all possibilities as a 20 bit integer, and every combination is simply the numbers between 0 and 1,048,575.
posted by cillit bang at 1:50 PM on February 9, 2007

I can't be of any real help, but Samuel Beckett's Molloy tackles this same problem, albeit with 16 sucking-stones and 4 pockets. I'm sure you can arrive at a better solution than he does, though.
posted by clockwork at 2:07 PM on February 9, 2007

I'm confused by your question of "ball picking algorithm" and your desire to enumerate all possible combinations. Why would you want to generate all possible combinations? What's your final objective?
posted by demiurge at 2:39 PM on February 9, 2007

I find this odd because you did realize that "this makes 4^10, which is over 1 million possibilities."

In the future, any problem where you can state there are X^Y possibilities, you can go through them all sequentially by treating the states as an Y-digit number in base X.
posted by vacapinta at 2:55 PM on February 9, 2007

Cillit Bang has it right... But I can't imagine any reason you would want to or need to do this... "ball picking algorithm"? you mean enumerate all possible states? cause thats just off on binary. Since a ball has to be in a box, (right?) then each ball has four states..
posted by magikker at 3:52 PM on February 9, 2007

My guess is that he wants to enumerate all possible states, then select one randomly. Hence the "picking" part. I'm rather confused as to why someone would want to do this, though. (Hopefully this isn't homework-filter.)
posted by chrisamiller at 4:39 PM on February 9, 2007

Thanks all! No, this definitely is not homework, I wish I were a student. This is for a hobby project. Now that I see your solutions it seems very obvious but I guess this is where my lack of any programming/math education shows.

I wouldn't enumerate everything if I was just going to pick a random choice afterwards. I want to make some calculations to decide which ball should go into which box. I am not sure if enumerating everything is the wisest choice, but I will know once I test that.
posted by davar at 5:01 PM on February 9, 2007

Hey davar, I'm a mathematician/theoretical computer scientist who spends more time than most people would consider normal thinking about balls and boxes (if you're trying to google this you'll find you have better luck searching for balls and bins). If you feel like sharing a little more information about your problem I can try to offer some ideas. My email is in my profile.
posted by louigi at 4:59 AM on February 10, 2007