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.

• Ivaylo Strandjev: You are missing [2,2,1]
• Yatharth Agarwal: @IvayloStrandjev Thanks. If you could edit my algorithm to make that fit it?
• mbeckish: possible duplicate of List all k-tuples with entries summing to n, ignoring rotations
• mbeckish: Search for "integer partition" to find more dupes.
• Yatharth Agarwal: @mbeckish Uh..., could you give a link to a dupe? In the question that you currently link, the order matters (but rotations don't) and here both do. Therefore the questions are and should be separate.

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

• Yatharth Agarwal: Thanks. 3 questions:- 1) Could you explain the stacking choices part? 2) I assume this is Java. Could you please explain how the Vector var works? Like a list where you can pop and append on both ends? 3) What exactly do you mean by dynamic programming? the Wikipedia page doesn't really help a lot...

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]]

• Yatharth Agarwal: Thanks a lot for this. Just one thing: any more readable language? Pseudocode or Python would do. I amn't able to understand it. Cuold you explain some of the Haskell idioms/syntax you used here?
• גלעד ברקן: @YatharthROCK I wish I could write it for you in Python but I am unfamiliar with it. I guess you would have to study a basic Haskell tutorial to learn it. The syntax [x,y | x <- [some list], y <- [some list]] is called a list comprehension and it creates all combinations of x and y, where x and y are taken from given lists. [something] is a list. nub removes duplicate elements from a list. sort sorts. map takes a function and applies it to all elements of a list. filter removes elements from a list according to a condition. ++ joins two lists. x:xs puts element x in list xs. hope that helps.

Answer 3

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)+"]");
 }
}

• Yatharth Agarwal: I want an arbitrary amount of buckets. This doesn't do that. You would probably need a recursive algorithm.
• Sudeep: yes for an arbitrary buckets you would need a recursive code also using dynamic programming to avoid used combinations.

Answer 4

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.

• Yatharth Agarwal: Are you sure about that? It would take freakishly long if there were a small number of buckets as compared to the balls...

Answer 5

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 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;
}