C++中N个球在M个箱子的排列组合

Question

我上周在网上问了一个关于C++中排列组合的问题（在C++中N个球放入M个盒子的组合列表）。

那些回答对我帮助很大，但我的问题现在变了。我想把这个Python函数转换成C++，并保持结果的顺序：

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

我对Python不太熟悉，尽管我看了文档，但还是不明白这个函数的意思。

Answer 1

你引用的Python代码实现了我在回答你问题时提到的算法。它的做法是遍历所有可能的方式，把r - 1个盒子放在n + r - 1个位置上，然后列出相邻位置之间的差值（这些差值表示被放入那个盒子的球的数量）。

Answer 2

你知道Python是解释型语言吧？你可以直接把不懂的代码行输入到Python里，看看会发生什么……先从小的值开始试。

我不太明白itertools.combinations()这个算法。

相关的文档在这里，里面有示例输出。要注意的是，combinations返回的值是“懒惰”的，所以你需要强制计算才能看到结果：

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

现在你明白combinations是干什么的吗？如果还不明白，试着玩一玩。

……还有“stops = indices + (size,)”的语法。

所以试试吧，它不会咬你的：

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

语法(x,)创建了一个只有一个元素的元组（这是一种不变的序列——就像一个你不能改变的list，不过用的是圆括号()而不是方括号[]）。你可以用[x]来创建一个只有一个元素的列表，但(x)会有歧义，因为圆括号也用于其他事情，比如函数参数和分组。

关于map()，……

看看文档，试着玩一玩，这并不难。

Answer 3

这段C++代码的结果和你的Python示例看起来是一样的。虽然它还不是完美的，但你可以理解这个算法，甚至可以使用这个实现。

#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()();
        }
    }
};

这个类的接口让你可以把它当作一个标准的生成器来使用。当所有可能的选项都被遍历完时，操作符()会抛出一个异常。

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