Перечень комбинаций из N шаров в коробках?

Question

Я хочу перечислить все возможные комбинации N шаров в A коробках.

пример: У меня есть 8 шары для раздачи в 3 коробках:

         box_1   box_2   box_3
case-1       8       0       0
case-2       0       8       0
case-3       0       0       8 
case-4       7       1       0
case-5       7       0       1
case-6       6       2       0
...

Моя первая проблема заключается в том, что для этого мне нужны циклы A , но я хочу, чтобы A и N для ввода пользователем. Так как же обойтись без записи всех возможных циклов, которые могут понадобиться пользователям?

a и N будут значения от 2 до ~ 800, поэтому это будет сильно требоваться во время вычислений, поэтому. Как оптимизировать этот алгоритм?

Буду признателен, если вы ответите мне на языке Python. спасибо за все вклады!

Answer 1

Это прекрасно работает, начиная с Python 2.6, ( 2.5-дружественная реализация itertools.permutations также доступна ):

>>> import itertools
>>> boxes = 3
>>> balls = 8
>>> rng = list(range(balls + 1)) * boxes
>>> set(i for i in itertools.permutations(rng, boxes) if sum(i) == balls)
{(0, 1, 7), (3, 1, 4), (0, 4, 4), (1, 0, 7), (4, 0, 4), (3, 0, 5), (1, 2, 5), (1, 7, 0), (0, 8, 0), (1, 4, 3), (6, 0, 2), (4, 3, 1), (3, 3, 2), (0, 5, 3), (5, 3, 0), (5, 1, 2), (2, 4, 2), (4, 4, 0), (3, 2, 3), (7, 1, 0), (5, 2, 1), (0, 6, 2), (6, 1, 1), (2, 2, 4), (1, 1, 6), (0, 2, 6), (7, 0, 1), (2, 1, 5), (0, 0, 8), (2, 0, 6), (2, 6, 0), (5, 0, 3), (2, 5, 1), (1, 6, 1), (8, 0, 0), (4, 1, 3), (6, 2, 0), (3, 5, 0), (0, 3, 5), (4, 2, 2), (1, 3, 4), (0, 7, 1), (1, 5, 2), (2, 3, 3), (3, 4, 1)}

Answer 2

псевдокод:

Enumerate(Balls, Boxes)
  if Boxes<=0 
    Error
  elseif Boxes=1 
    Box[1] = Balls
    PrintBoxes
  else
    forall b in 0..Balls 
      Box[Boxes] = b
      Enumerate(Balls-b, Boxes-1)
    endfor
  endif
end

Объяснение

Начните с первого ящика, если ящиков нет, пожалуйтесь и выходите. Если это последний заполненный ящик, бросьте все оставшиеся шары и покажите результат. Если есть еще коробки, сначала добавьте 0 шаров и повторите процедуру с другими блоками. Затем добавьте 1, шарик 2 шарика, пока не останется шариков.

Чтобы показать, что алгоритм работает, я приведу пример с реальными значениями, 3 шара и 2 поля.

У нас есть массив коробок с именем Box, и каждый бокс может содержать любое количество шариков (значение). PrintBoxes печатает текущее значение блоков.

Box = (0,0)
Enumerate(3, 2)
  b=0
  Box = (0,0)
  Enumerate(3,1)
    Box = (3,0) 
    Print!
  b=1 
  Box = (0,1)
  Enumerate(2,1)
    Box = (2,1)
    Print!
  b=2
  Box = (0,2)
  Enumerate(1,1)
    Box = (1,2)
    Print!
  b=3   
  Box = (0,3)
  Enumerate(0,1)
    Box = (0,3)
    Print!

 Output:

 (3,0)
 (2,1)
 (1,2)
 (0,3)

 Which are all the combinations.

Еще один пример с 3 коробками и 3 шарами:

Box = (0,0,0)
Enumerate(3, 3)
  b=0
  Box = (0,0,0)
  Enumerate(3,2)
    b=0
    Box = (0,0,0)
    Enumerate(3,1)
      Box = (3,0,0)
    b=1
    Box = (0,1,0)
    Enumerate(2,1)
      Box = (2,1,0)
    b=2
    Box = (0,2,0)
    Enumerate(1,1)
      Box = (1,2,0)
    b=3
    Box = (0,3,0)
    Enumerate(0,1)
      Box = (0,3,0)
  b=1 
  Box = (0,0,1)
  Enumerate(2,2)
    b=0
    Box = (0,0,1)
    Enumerate(2,1)
      Box = (2,0,1)
    b=1
    Box = (0,1,1)
    Enumerate(1,1)
      Box = (1,1,1)
    b=2
    Box = (0,2,1)
    Enumerate(0,1)
      Box = (0,2,1)
  b=2
  Box = (0,0,2)
  Enumerate(1,2)
    b=0
    Box = (0,0,2)
    Enumerate(1,1)
      Box = (1,0,2)
    b=1
    Box = (0,1,2)
    Enumerate(0,1)
      Box = (0,1,2)
  b=3   
  Box = (0,0,3)
  Enumerate(0,2)
    b=0
    Box = (0,0,3)
    Enumerate(0,1)
      Box = (0,0,3)

Output
(3,0,0)
(2,1,0)
(1,2,0)
(0,3,0)
(2,0,1)
(1,1,1)
(0,2,1)
(1,0,2)
(0,1,2)
(0,0,3)

Answer 3

См. itertools.combination_with_replacement в 3.1 для примера, написанного на python. Кроме того, в комбинаторике обычно превращают проблему комбинации с заменой в обычную проблему комбинации без замены, которая уже встроена в 2.6 itertools. Это имеет преимущество в том, что не генерирует отброшенные кортежи, такие как решения, основанные на продукте или перестановке. Вот пример, использующий стандартную (n, r) терминологию, которая в вашем примере будет (A, N).

import itertools, operator
def combinations_with_replacement_counts(n, r):
    size = n + r - 1
    for indices in itertools.combinations(range(size), n-1):
        starts = [0] + [index+1 for index in indices]
        stops = indices + (size,)
        yield tuple(map(operator.sub, stops, starts))

>>> list(combinations_with_replacement_counts(3, 8))
[(0, 0, 8), (0, 1, 7), (0, 2, 6), (0, 3, 5), (0, 4, 4), (0, 5, 3), (0, 6, 2), (0, 7, 1), (0, 8, 0), (1, 0, 7), (1, 1, 6), (1, 2, 5), (1, 3, 4), (1, 4, 3), (1, 5, 2), (1, 6, 1), (1, 7, 0), (2, 0, 6), (2, 1, 5), (2, 2, 4), (2, 3, 3), (2, 4, 2), (2, 5, 1), (2, 6, 0), (3, 0, 5), (3, 1, 4), (3, 2, 3), (3, 3, 2), (3, 4, 1), (3, 5, 0), (4, 0, 4), (4, 1, 3), (4, 2, 2), (4, 3, 1), (4, 4, 0), (5, 0, 3), (5, 1, 2), (5, 2, 1), (5, 3, 0), (6, 0, 2), (6, 1, 1), (6, 2, 0), (7, 0, 1), (7, 1, 0), (8, 0, 0)]

Answer 4

Хорошая идея - использовать генератор python, как это было сделано выше, но здесь есть более простая (не уверенная в эффективности) версия:

def balls_in_baskets(balls=1, baskets=1):
    if baskets == 1:
        yield [balls]
    elif balls == 0:
        yield [0]*baskets
    else:
        for i in xrange(balls+1):
            for j in balls_in_baskets(balls-i, 1):
                for k in balls_in_baskets(i, baskets-1):
                    yield j+k

for i in balls_in_baskets(8,3):
    print i

Answer 5

Вы можете определить рекурсивный генератор , который создает суб-генератор для каждого цикла for, который вы хотите вкладывать, например:

def ballsAndBoxes(balls, boxes, boxIndex=0, sumThusFar=0):
    if boxIndex < (boxes - 1):
        for counter in xrange(balls + 1 - sumThusFar):
            for rest in ballsAndBoxes(balls, boxes,
                                      boxIndex + 1,
                                      sumThusFar + counter):
                yield (counter,) + rest
    else:
        yield (balls - sumThusFar,)

Когда вы вызываете это на верхнем уровне, он принимает только аргументы 'balls' и 'boxes', остальные присутствуют по умолчанию, так что рекурсивный вызов может передавать разные вещи. Он выдаст кортежи целых чисел (длины 'ящики'), которые являются вашими значениями.

Чтобы получить точное форматирование, указанное вами в начале этого поста, вы можете назвать его примерно так:

BALLS = 8
BOXES = 3
print '\t',
for box in xrange(1, BOXES + 1):
    print '\tbox_%d' % (box,),
print
for position, value in enumerate(ballsAndBoxes(BALLS, BOXES)):
    print 'case-%d\t\t%s' % (position + 1, 
                             "\t".join((str(v) for v in value)))

Answer 6

def iterate_assignments(N, K):
    buckets = [0] * K
    buckets[0] = K
    while True:
        yield buckets
        if buckets[-1] == N:
            return
        non_empty_buckets = sorted([i for i, count in enumerate(buckets) if count > 0])
        if non_empty_buckets[-1] == K - 1:
            temp = buckets[-1]
            buckets[-1] = 0
            buckets[non_empty_buckets[-2] + 1] = temp + 1
            buckets[non_empty_buckets[-2]] -= 1
        else:
            buckets[non_empty_buckets[-1]] -= 1
            buckets[non_empty_buckets[-1] + 1] += 1

Это решение в python, которое эффективно выдает все возможные назначения из N шаров для K блоков в памяти O (K) и времени O (# возможных назначений).

Начните с задания, в котором все шары находятся в крайнем левом ведре (для понимания предположим, что все ведра расположены слева направо). Создайте все последующие задания, постепенно перемещая шары вправо следующим образом:

(1) если самый правый шар находится в самом правом ведре, найдите следующий самый правый шар и переместите оба этих шара в ведра один справа от следующего самого правого шара (2) Если самый правый шар находится где-либо еще, переместите его на одно ведро вправо

Из этой схемы ясно, почему она генерирует только уникальные комбинации. Чтобы понять, почему получается все уникальных комбинаций, нужно немного больше подумать. Я могу попытаться формализовать доказательство, если людям это интересно, но сейчас я пропускаю:)

Answer 7

Если вы просто хотите узнать количество возможностей, а не перечислять их, тогда будет работать следующая формула:

Возможности = (N + A-1) C N = (N + A-1)! / (N! X (A-1)!)

Где aCb (a выбор b) - это количество способов выбора комбинаций размера b из набора размеров a.

! обозначает факториал, то есть 5! = 5 * 4 * 3 * 2 * 1, n! = n * (n-1) * (n-2) * ... * 3 * 2 * 1. Извините, если я учу вас, как сосать яйца.

В питоне:

from math import factorial as f
balls=N
boxes=A
def p(balls,boxes):
    return f(balls+boxes-1)/f(balls)/f(boxes-1)
p(3,2)
  4
p(3,3)
  10

, что согласуется с примерами Gamecat.

Чтобы объяснить, почему формула работает, давайте посмотрим на пять шаров и 3 коробки. Обозначим шары звездочками. Мы хотим разместить 3-1 = 2 разделительные линии, чтобы разбить шары на 3 отсека.

Например, мы могли бы иметь

* | * | *   *   *        (1,1,3)
*   * | *   *   * |      (2,3,0)
*   *   *   *   * |  |   (5,0,0)

7 символов можно заказать 7! = 5040 возможных способов. Поскольку все шары одинаковы, нас не беспокоит их порядок, поэтому мы делим на 5 !. Точно так же нас не беспокоит порядок разделительных линий, поэтому мы делим на 2 !. Это дает нам 7C5 = 7! / (5! * 2!) = 21 возможность.

Статья в Википедии о Комбинации содержит раздел «Количество комбинаций с повторением», в котором вопрос подсчета комбинаций перефразирован вкуснее (пончики и кусочки фруктов вместо шариков).

Если вы хотите перечислить комбинации, будьте осторожны, как быстро растет число. Для 20 шаров и 9 коробок существует более 3 миллионов возможностей!

edit: мой предыдущий ответ сравнил эту проблему с целочисленными разделами, чтобы показать, как быстро растет число возможностей. Мой новый ответ больше относится к исходному вопросу.

Answer 8

, если вы хотите использовать свою собственную функцию, ответ от Gamecat может сработать еще либо используйте http://probstat.sourceforge.net/, это очень быстро (написано в c)

или itertools в Python 2.6