Finding all distributions of A apples amongst B baskets

Question

We have A apples, B baskets.

How would you write the algorithm that lists every possible distribution for baskets. One basket can contain zero or max apples.

For example: A = 6, B = 4 (6 apples, 4 baskets).

d1 = 6 0 0 0

d2 = 5 1 0 0

d3 = 5 0 1 0

d4 = 4 2 0 0

d5 = 3 0 0 3

.......

...... so on....

Answer 1

You can generate them recursively by adding 0 to apples_left apples to the current bucket and returning all solutions for the current bucket + the remaining buckets with apples_left minus apples taken for this bucket. I think code explains it best here, so here's some Python code:

def allocations(apples, baskets):
  if baskets == 0:
    if apples == 0:
      yield []
    return
  for a in xrange(apples+1):
    for alloc in allocations(apples-a, baskets-1):
      yield [a] + alloc

for i, alloc in enumerate(allocations(6, 4)):
  print 'd%d = %s' % (i+1, ' '.join(map(str, alloc)))

Outputs

d1 = 0 0 0 6
d2 = 0 0 1 5
d3 = 0 0 2 4
d4 = 0 0 3 3
...
d83 = 5 1 0 0
d84 = 6 0 0 0

Full output

Answer 2

int basket[6];
void walk(int iBasket, int nRemain){
  if (iBasket == 6-1){
    basket[iBasket] = nRemain;
    // print baskets
  }
  else {
    for (i = 0; i <= nRemain; i++){
      basket[iBasket] = i;
      walk(iBasket+1, nRemain - i);
    }
  }
}

void main(){
  walk(0, 6);
}

Answer 3

int apples;
int baskets;
cin >> apples >> baskets;
vector<int>(apples + baskets - 1, 0);
for(int i = baskets - 1; i < apples + baskets - 1; ++i)
 v[i] = 1;
do
{
 //first basket untill 1st 0
 //second basket from 1st to 2nd 0
 //third basket from 2nd to 3th 0
 //...
 //last basket from (basket - 1)th 0 to the end of vector
}next_permutation(v.begin(), v.end());

Answer 4

In case you need an optimized version, you can also use an algorithm for generating combinations, which is provided by libraries like Python's itertools. See my answer to this this question

from itertools import combinations, tee 


def diffed_tuple(t):
    t2, t1 = tee(t)
    for x in t2:
        break
    return tuple(e2 - e1 for e2, e1 in zip(t2, t1))



# --The Algorithm--
def compositions(n, k):
    for t in combinations(range(n+k), k+1):
        yield tuple(e-1 for e in diffed_tuple(t))