Algorithm to partition/distribute sum between buckets in all unique ways

Question

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.

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 SO using all wordings that I could think of, but only found results for distributing in the most even way, not all unique ways.

Answer 1

Its bit easier for me to code few lines than writing a 5-page essay on algorithm. The simplest version to think of:

vector<int> ans;

void solve(int amount, int buckets, int max){
  if(amount <= 0) { printAnswer(); return;}
  if(amount > buckets * max) return; // we wont be able to fulfill this request anymore

  for(int i = max; i >= 1; i--){
    ans.push_back(i);
    solve(amount-i, buckets-1, i);
    ans.pop_back();
  } 
}

void printAnswer(){
  for(int i = 0; i < ans.size(); i++) printf("%d ", ans[i]);
  for(int i = 0; i < all_my_buckets - ans.size(); i++) printf("0 ");
  printf("\n");
}

Its also worth improving to the point where you stack your choices like solve( amount-k*i, buckets-k, i-1) - so you wont create too deep recurrence. (As far as I know the stack would be of size O(sqrt(n)) then.

Why no dynamic programming?

We dont want to find count of all those possibilities, so even if we reach the same point again, we would have to print every single number anyway, so the complexity will stay the same.

I hope it helps you a bit, feel free to ask me any question

Answer 2

Here's something in Haskell that relies on this answer:

import Data.List (nub, sort)

parts 0 = []
parts n = nub $ map sort $ [n] : [x:xs | x <- [1..n`div`2], xs <- parts(n - x)]

partitions n buckets = 
  let p = filter (\x -> length x <= buckets) $ parts n 
  in map (\x -> if length x == buckets then x else addZeros x) p  
    where addZeros xs = xs ++ replicate (buckets - length xs) 0


OUTPUT:
*Main> partitions 5 3
[[5,0,0],[1,4,0],[1,1,3],[1,2,2],[2,3,0]]

Answer 3

A completely different method, but if you don't care about efficiency or optimization, you could always use the old "bucket-free" partition algorithms. Then, you could filter the search by checking the number of zeroes in the answers.

For example [1,1,1,1,1] would be ignored since it has more than 3 buckets, but [2,2,1,0,0] would pass.

Answer 4

This is called an integer partition.

Fast Integer Partition Algorithms is a comprehensive paper describing all of the fastest algorithms for performing an integer partition.

Answer 5

If there are only three buckets this wud be the simplest code.

for(int i=0;i<=5;i++){
        for(int j=0;j<=5-i&&j<=i;j++){
            if(5-i-j<=i && 5-i-j<=j)
                System.out.println("["+i+","+j+","+(5-i-j)+"]");
        }
}

Answer 6

Just adding my approach here along with the others'. It's written in Python, so it's practically like pseudocode.

My first approach 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

Just for comprehensiveness, here's another answer stolen from MJD written in Perl:

#!/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;
}