Поиск всех распределений яблок среди корзин B

Question

У нас есть яблоки А, корзины В.

Как бы вы написали алгоритм, в котором перечислены все возможные распределения для корзин. Одна корзина может содержать ноль или максимум яблок.

Например: A = 6, B = 4 (6 яблок, 4 корзины).

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

.......

...... и так далее ...

Answer 1

Если вам нужна оптимизированная версия, вы также можете использовать алгоритм для генерации комбинаций, который предоставляется библиотеками вроде Python itertools.Смотрите мой ответ на этот этот вопрос

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

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

Вы можете сгенерировать их рекурсивно, добавив от 0 до apples_left яблок в текущее ведро и вернув все решения для текущего ведра + оставшиеся ведра с apples_left минус яблоки, взятые для этого ведра. Я думаю, что код объясняет это лучше всего здесь, поэтому вот код Python:

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

Выходы

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

Полный вывод