The Problem
I need an algorithm that does this:
Find all the unique ways to partition a given sum across 'buckets' not caring about order
I hope I was clear reasonably coherent in expressing myself. I didn't put in code as the algorithm isn't fleshed out yet Done.
Example
For the sum 5 and 3 buckets, what the algorithm should return is:
[5, 0, 0]
[4, 1, 0]
[3, 2, 0]
[3, 1, 1]
[2, 2, 1]
Disclaimer
I'm sorry if this question might be a dupe, but I don't know exactly what these sort of problems are called. Still, I searched on Google and Math.SE using all wordings that I could think of, but only found results for distributing in the most even way, not all unique ways.
Solution
OK, so I tinkered around a bit and came up with a solution. Since I didn't want to rob the awesome guys here who were faster than me of their rep, I'm not accepting my own answer, but putting it here. It's in Python which is practically like pseudocode with a compiler.
My first attempt worked, but it was horribly inefficient:
def intPart(buckets, balls):
return uniqify(_intPart(buckets, balls))
def _intPart(buckets, balls):
solutions = []
# base case
if buckets == 1:
return [[balls]]
# recursive strategy
for i in range(balls + 1):
for sol in _intPart(buckets - 1, balls - i):
cur = [i]
cur.extend(sol)
solutions.append(cur)
return solutions
def uniqify(seq):
seen = set()
sort = [list(reversed(sorted(elem))) for elem in seq]
return [elem for elem in sort if str(elem) not in seen and not seen.add(str(elem))]
Here's my reworked solution. It completely avoids the need to 'uniquify' it by the tracking the balls in the previous bucket using the max_
variable. This sorts the lists and prevents any dupes.
def intPart(buckets, balls, max_ = None):
# init vars
sols = []
if max_ is None:
max_ = balls
min_ = max(0, balls - max_)
# assert stuff
assert buckets >= 1
assert balls >= 0
# base cases
if (buckets == 1):
if balls <= max_:
sols.append([balls])
elif balls == 0:
sol = [0] * buckets
sols.append(sol)
# recursive strategy
else:
for there in range(min_, balls + 1):
here = balls - there
ways = intPart(buckets - 1, there, here)
for way in ways:
sol = [here]
sol.extend(way)
sols.append(sol)
return sols
Best Answer
This is Perl, but the algorithm is straightforward and should be easy to implement in any language:
The function
part
gets two arguments: $n$ is the total number of beans that you want (5 in your example) and $b$ is the number of buckets (3 in your example). It also gets an auxiliary argument, $min$, which is the smallest permissible bucket value. This defaults to 0 if it is not supplied.The function is recursive, just as you suggested. The base case is no buckets, $b=0$. If there are no beans to put into the buckets ($n=0$ also) then this can be satisfied in exactly one way, by an empty array of buckets
[]
. Otherwise there is no solution because there are beans left over but no buckets to put them in.If $b>0$ then the function will accumulate a list of possible partitions of $n$ beans into $b$ buckets in the array
@partitions
. It will do this by selecting the number of beans to go into the first bucket ($first$), recursively allocating the remaining beans into $b-1$ buckets, and assembling the two into a complete solution, which it will append to@partitions
. This is just what you suggested in your question.The number of the beans in the first bucket must be at least $min$, and at most $n$, the total number of beans.
The function then calls itself recursively: there are $n-first$ beans to allocate to $b-1$ buckets, but no bucket can have fewer than $first$ beans. This last bit is the only tricky part: it ensures that the number of beans never decreases from each bucket to the next, and so that each generated partition is unique. (Without this restriction,
[1,2,2]
,[2,1,2]
, and[2,2,1]
would be different solutions. With this restriction, only[1,2,2]
is generated.)The recursive call returns a number of partitions of $n-first$ beans into $b-1$ buckets. $first$ is appended to each of these (that's
[$first, @$sp]
, which makes a single array out of$first
and the contents of$sp
) and the resulting partitions of $n$ beans into $b$ buckets are pushed onto@partitions
. When this has been done for each permissible value of $first$, the complete@partitions
list is returned.To test your example, I did:
Which printed:
To get the partitions with largest element first, just change
[$first, @$sp]
to[@$sp, $first]
.Some minor optimization are possible. For example, if $n < b\cdot min$ then one can halt the recursion immediately, returning no solutions.