Enumeration of combinations of N balls in A boxes?

Question

Hi,

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

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 2

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 3

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 4

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 5

Hi, thanks all for your answer, I still working on it :o) I feel that I'm learning much.

thanks Gamecat for your addendum. It should help me tomorrow morning to understand. ;o)

Silentghost : I will upgrad my python version but as scientist, I use enthough python distribution...probably not to date :oD

Glyph, can you post me how you call your function (because of the last 2 fixed arguments)? Why there's no "return"? I will look about "yield" that I have never used yet, I assume that it should bring me the answer. Thanks.

Great place to learn! I plebicite that place!

Answer 6

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.

Answer 7

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