Enumeration of combinations of N balls in A boxes?

Question

I want to enumerate all possible combinations of N balls in A boxes.

example: I have 8 balls to deal in 3 boxes :

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

My first problem is that I need A loops to perform this but I want that A and N to be user's inputs. So how to do without writing all possible number of loops users could need?

a and N will be value between 2 and ~800, so it will be strongly demanding in computation time so. How to optimize that algorithm?

I would be grateful if you answer me using python language. thanks for all contributions!

Answer 1

This works just fine starting with python 2.6, (2.5-friendly implementation of itertools.permutations is available as well):

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

Pseudocode:

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

Explanation

Start at the first box, if there are no boxes, complain and quit. If it is the last box to be filled, drop all remaining balls and show the result. If there are more boxes, first add 0 balls and repeat the procedure with the other boxes. Then add 1, ball 2 balls until there are no balls left.

To show, that the algorithm works, I give an example with real values, 3 balls and 2 boxes.

We have an array of boxes called Box, and each box can hold any number of balls (the value). PrintBoxes prints the current value of the boxes.

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.

Another example with 3 boxes and 3 balls:

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

See itertools.combinations_with_replacement in 3.1 for an example written in python. Additionally, it's common in combinatorics to transform a combination-with-replacement problem into the usual combination-without-replacement problem, which is already builtin in 2.6 itertools. This has the advantage of not generating discarded tuples, like solutions based on product or permutation. Here's an example using the standard (n, r) terminology, which would be (A, N) in your example.

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

It is good idea to use python generator, as it was done above but here is more straightforward (not sure about efficency) version:

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

You can define a recursive generator which creates a sub-generator for each 'for loop' which you wish to nest, like this:

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

When you call this at the top level, it will take only a 'balls' and 'boxes' argument, the others are there as defaults so that the recursive call can pass different things. It will yield tuples of integers (of length 'boxes') that are your values.

To get the exact formatting you specified at the top of this post, you could call it something like this:

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

This is a solution in python which efficiently yields all possible assignments of N balls to K buckets in O(K) memory and O(# possible assignments) time.

Start with an assignment where all balls are in the left-most bucket (for the purposes of understanding, assume all buckets are arranged left-to-right). Generate all later assignments by progressively moving balls to the right in the following fashion:

(1) if the right-most ball is in the right-most bucket, find the next right-most ball and move both of these balls into the buckets one to the right of the next right-most ball (2) If the right-most ball is anywhere else, move it one bucket to the right

From this scheme, its clear to see why this only generates unique combinations. It takes a bit more thought to see why this produces all unique combinations. I can attempt to formalize a proof if people are interested, but I'm skipping for now :)

Answer 7

if you want to use your own function answer by Gamecat may work else either use http://probstat.sourceforge.net/ , it is very fast (written in c)

or itertools in python 2.6

Answer 8

If you simply want to know the number of possibilities, instead of listing them, then the following formula will work:

Possibilities = (N+A-1) C N = (N+A-1)!/(N!x(A-1)!)

Where aCb (a choose b) is the number of ways of choosing combinations of size b from a set of size a.

! denotes the factorial ie 5!=5*4*3*2*1, n!=n*(n-1)*(n-2)*...*3*2*1. Sorry if I'm teaching you how to suck eggs.

In python:

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

which agrees with Gamecat's examples.

To explain why the formula works, let's look at five balls and 3 boxes. Denote balls as asterisks. We want to place 3-1=2 dividing lines to split the balls into 3 compartments.

For example, we could have

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

7 symbols can be ordered in 7!=5040 possible ways. Since all the balls are the same, we aren't worried about the order of the balls, so we divide by 5!. Similarly, we aren't worried about the order of the dividing lines so we divide by 2!. This gives us 7C5=7!/(5!*2!)=21 possibilities.

The Wikipedia article on Combinations has a section "Number of combinations with repetition" which is the counting combinations question rephrased in a tastier way (donuts and pieces of fruit instead of balls).

If you want to list the combinations, beware how quickly the number grows. For 20 balls and 9 boxes, there are over 3 million possibilities!

edit: my previous answer compared this problem to integer partitions to show how quickly the number of possibilities grows. My new answer is more relevant to the original question.