[Math] Algorithm to partition sum between buckets in all unique ways

algorithmsinteger-partitions

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:

      #!/usr/bin/perl

      sub part {
        my ($n, $b, $min) = @_;
        $min = 0 unless defined $min;

        # base case
        if ($b == 0) {
          if ($n == 0) { return ( [] ) }
          else         { return ()     }
        }

        my @partitions;
        for my $first ($min .. $n) {
          my @sub_partitions = part($n - $first, $b-1, $first);
          for my $sp (@sub_partitions) {
            push @partitions, [$first, @$sp];
          }
        }
        return @partitions;
      }

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:

    for my $p ( part(5, 3) ) {
      print "@$p\n";
    }

Which printed:

0 0 5
0 1 4
0 2 3
1 1 3
1 2 2

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.

Related Question