The algorithm for sharing / distributing the amount between buckets in all unique ways

Question

Problem

I need an algorithm that does this:

Find all the unique ways to divide this amount into "buckets" without worrying about the order

I hope I was clear I reasonably agree to express myself.

Example

For the sums of 5 and 3 codes that the algorithm should return:

[5, 0, 0]
[4, 1, 0]
[3, 2, 0]
[3, 1, 1] [2, 2, 1]

Renouncement

I apologize if this question can be a hoax, but I don’t know exactly what these problems are called. However, I searched on Google and SO using all the formulations I could think of, but only found the results for distribution in the most even form, and not in all unique ways.

Answer 1

, 5- . :

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

, , solve( amount-k*i, buckets-k, i-1) - . ( , O (sqrt (n)).

?

, , , , .

, , .

Answer 2

- Haskell, :

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

, , "" . , .

, [1,1,1,1,1] , , [2,2,1,0,0] .

Answer 4

.

- , .

Answer 5

, wud .

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

. Python, .

, :

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

. "" max_. :

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

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