permutations of N balls in M boxes in C++

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,)
       开发者_C百科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.

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.

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(...) {}

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