I’m coding a puzzle-solver, and I need to be able to generate each game state. To do so, I need an algorithm related in some way to combinations but I can’t figure it out. Here is a sample problem that the algorithm needs to be able to solve:
“There are 4 balls and 3 baskets. Each ball must go into a basket and each basket may hold a maximum of 2 balls. List all possible combinations of baskets holding balls. Order does not matter.”
Possibility 1: 2 baskets with 2 balls, 2 baskets with 0 balls OR baskets = [2, 2, 0] *(order does not matter)
Possibility 2: 1 basket with 2 balls, 2 baskets with 1 ball OR baskets = [2, 1, 1] *(order does not matter)
Possibility N-1: …
Possibility N: …
Note: [2, 2, 0] and [0, 2, 2] are counted as equal and only one should be produced as a possibility.
To recap, I need a way to find all possibilities for a situation like above; the number of balls and baskets may vary. Please let me know if anything needs to be clarified or if I left something out. Thanks!
Best Answer
Let's say you have m baskets and n balls, then there are only valid combinations if $0 \leq n \leq 2*m$. If n is outside of this range, then there are 0 possibilities.
Each of your possibilities is a partition of n with a length of m or less (if the partition has length less than m, pad it with zeroes until it is of length m). Furthermore, only partitions with entries in ${0,1,2}$ are valid.
See http://mathworld.wolfram.com/Partition.html if you are unfamiliar with partitions.