List of combinations of N balls in M boxes in C++

Question

I would like to write a function that generate an array of tuples containing all possible permutations of N balls in M boxes in C++.

The order (Edit : in the resulting list) is not important, just that the first must be (N,0,...,0) and the last (0,0,...,N).

I didn't find such an implementation on the net in C++, only permutations of chars or calculations of the number of permutations...

Any ideas ?

Answer 1

There's a neat trick to solving this. Imagine that we took the n balls and m − 1 boxes and put them in a row of length n + m − 1 (with the boxes mixed up among the balls). Then put each ball in the box to its right, and add an mth box at the right that gets any balls that are left over.

This yields an arangement of n balls in m boxes.

It is easy to see that there are the same number of arrangements of n balls in sequence with m − 1 boxes (the first picture) as there are arrangements of n balls in m boxes. (To go one way, put each ball in the box to its right; to go the other way, each box empties the balls into the positions to its left.) Each arrangement in the first picture is determined by the positions where we put the boxes. There are m − 1 boxes and n + m − 1 positions, so there are ^{n + m − 1}C_m − 1 ways to do that.

So you just need an ordinary combinations algorithm (see this question) to generate the possible positions for the boxes, and then take the differences between successive positions (less 1) to count the number of balls in each box.

In Python it would be very simple since there's a combinations algorithm in the standard library:

from itertools import combinations

def balls_in_boxes(n, m):
    """Generate combinations of n balls in m boxes.

    >>> list(balls_in_boxes(4, 2))
    [(0, 4), (1, 3), (2, 2), (3, 1), (4, 0)]
    >>> list(balls_in_boxes(3, 3))
    [(0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0), (3, 0, 0)]

    """
    for c in combinations(range(n + m - 1), m - 1):
        yield tuple(b - a - 1 for a, b in zip((-1,) + c, c + (n + m - 1,)))

Answer 2

You could solve this problem recursively using a queue of vectors where you have a function with a for-loop that loops over the number of N balls, placing each of the N balls in a single box of the M boxes that is represented by a vector of size M. It then calls the same function recursively, but passes in a reduced index value for where to set the value of the N balls in the vector. The base-case of the recursive calls would initialize the queue with the vectors of size M, and would create N vectors, with each vector having an initialize slot (in this case slot 0) set with an individual value from the N balls.

Edit: I've changed the code so that it now reflects the multi-combinations, not the permutations. This required the addition of a new struct box_t that allows use to properly store the boxes in the queue, and tell when we hit repeats.

struct box_t
{
    vector<int> boxes;
    int flag;  //this flag lets us know if we're repeating a value
    box_t(int num_boxes): boxes(num_boxes), flag(0) {}
};

typedef queue<box_t> comb_queue;

comb_queue multi_combinations(int num_boxes, int ball_index)
{
    if (ball_index == 0)
    {
        comb_queue initial_queue;

        //initialize our queue with M vectors that will have 
        //only one of the "boxes" initialized with a value
        for (int i=0; i < num_boxes; i++)
        {
            box_t temp(num_boxes);
            temp.boxes[i] += 1;
            initial_queue.push(temp);
        }

        return initial_queue;
    }

    //here is our recursive call
    comb_queue box_combinations = multi_combinations(num_boxes, ball_index - 1);
    int queue_size = box_combinations.size();

    for (int i=0; i < queue_size; i++)
    {
        box_t boxes = box_combinations.front();
        box_combinations.pop();

        if (boxes.flag)
        {
            //this combination has already been processed, so place back in the queue
            //and move on
            box_combinations.push(boxes);
            continue;
        }

        for (int j=0; j < num_boxes; j++)
        {
             //increment the ball-count in each of the boxes
             boxes[j] += 1;
             box_combinations.push(boxes);

             //remove the ball we just added from the box slot for the next loop
             boxes[j] -= 1;
        }

        //finally place the box_t we've been processing back in the queue, but with the
        //repeat flag set
        boxes.flag = 1;
        box_combinations.push(boxes);
    }

    return box_combinations;
}

Then call the function like:

comb_queue all_multi_combinations = multi_combinations(M, (N-1));

The output will now be a queue of vectors that have the numbers of balls in each box for each multi-combination of N balls in M boxes.

Answer 3

List of combinations of N balls in M boxes = k + List of combinations of (N-k) balls in (M-1) boxes for every k from 0 to N. Try code this recursively.

Answer 4

Actually there is one. Take a look at: http://photon.poly.edu/~hbr/boost/combinations.html

It is not in boost but follows the same principles as is easily visible from the name.