[ACCEPTED]-List of combinations of N balls in M boxes in C++-combinations

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

This yields an 19 arangement of n balls in m boxes.

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

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

In 2 Python it would be very simple since there's 1 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,)))

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

You could solve this problem recursively 17 using a queue of vectors where you have 16 a function with a for-loop that loops over 15 the number of N balls, placing each of the 14 N balls in a single box of the M boxes that 13 is represented by a vector of size M. It 12 then calls the same function recursively, but 11 passes in a reduced index value for where 10 to set the value of the N balls in the vector. The 9 base-case of the recursive calls would initialize 8 the queue with the vectors of size M, and 7 would create N vectors, with each vector 6 having an initialize slot (in this case 5 slot 0) set with an individual value from 4 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 3 output will now be a queue of vectors that 2 have the numbers of balls in each box for 1 each multi-combination of N balls in M boxes.

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

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