permutations of N balls in M boxes in C++

Question

I asked a question last week about permutations in C++ (List of combinations of N balls in M boxes in C++).

The answers have helped me a lot but my problem has now changed. What i would like to do is a translation from this python function to C++, keeping the same order in the result :

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

I've no skill in python and despite my readings of the doc, I don't understand this function.

Answer 1

You know python is interpreted, right? You can just type the lines you don't understand directly into python and see what happens ... start with small values first.

I don't understand the itertools.combinations() algorithm

The documentation is here, and includes example output. Note that the value returned from combinations is lazy, so you need to force evaluation to see it:

>>> import itertools
>>> itertools.combinations(range(4), 2)
<itertools.combinations object at 0x979a964>
>>> list(itertools.combinations(range(4), 2))
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

Is it clear what combinations does now? If not, have a play with it.

... and the syntax of "stops = indices + (size,)"

So try it, it won't bite:

>>> indices=list(itertools.combinations(range(4), 2))[0]
>>> size=4
>>> stops=indices + (size,)
>>> indices
(0, 1)
>>> stops
(0, 1, 4)

The syntax (x,) creates a one-element tuple (an invariant sequence - just like a list you can't change but with round parentheses () instead of square ones []). You can use [x] to create a one-element list, but (x) would be ambiguous since round parentheses are also used for other things, like function arguments and grouping.

Concerning map(), ...

Read the doc, have a play with it, it isn't hard.

Answer 2

This C++ code seems to have the same results as your python sample. It is far from the perfect one, still you could understand the algorithm and even use this implementation.

#include <deque>
typedef std::deque<size_t> BoxList;

class Generator {
    size_t boxNum, ballNum, ownBox;
    Generator* recursive;
public:
    ~Generator() { if ( recursive == NULL ) delete recursive; }
    Generator( size_t boxes, size_t balls ) : boxNum(boxes), ballNum(balls) {
        if ( boxes > 1 ) {
            recursive = new Generator( boxes-1, balls );
            ownBox = 0;
        } else {
            recursive = NULL;
            ownBox = balls;
        }
    }
    BoxList operator()() {
        if ( ownBox > ballNum ) throw 1;
        if ( boxNum <= 1 ) return BoxList( 1, ownBox++ );
        try {
            BoxList res = recursive->operator()(); 
            res.push_front( ownBox );
            return res;
        }
        catch(...) {
            delete recursive;
            ownBox++;
            recursive = new Generator( boxNum-1, ballNum-ownBox );
            return operator()();
        }
    }
};

Class interface allows you to use it as a standard generator. Operator () will generate exception when all possible options have been already iterated.

Generator g( boxes, balls );
try{
    while( true )
        g();
}
catch(...) {}

Answer 3

The Python code you quoted is implementing the algorithm I described in my answer to your question: it's iterating over the possible ways to place r − 1 boxes in n + r − 1 positions, and then making a list of the differences between adjacent positions (which count the number of balls that are swept into that box).