First, you can check this thread for more information on your algorithm. You will discover than the number of lists you generate is (n+r-1)C(r-1), this may help. There is multiple ways to translate this code, but I'll give you two.
The iterative way
First, in C++, the generator pattern is not very common. Depending on what you want to do, most of the time you prefer to actually allocate the memory for all this output at inception, compute the date, then return the full matrix. Second, you can not recurse this way in C++, you will ruin your stack very quickly. So you need an iterative version of your algorithm. Here is how to do it (with iterators, as we like them in C++).
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <boost/math/special_functions/binomial.hpp>
#include <boost/numeric/conversion/cast.hpp>
using namespace std;
vector<vector<size_t>> gen_matrix(unsigned int n, unsigned int r)
{
vector<vector<size_t>> res;
if(r < 1) return res;
// reserve memory space
// this will throw positive_overflow if size is too big to be represented as size_t
// this can also throw out_of_memory if this is size_t-representable but memory is too small.
double result_size = boost::math::binomial_coefficient<double>(n + r - 1, r - 1);
res.reserve(boost::numeric_cast<size_t>(result_size));
vector<size_t> current(r, 0);
current.front() = n;
res.push_back(current);
vector<size_t>::iterator inc = next(current.begin()); // what we increment
while(inc != current.end())
{
while(current.front() != 0)
{
(*inc)++;
current.front()--;
res.push_back(current);
while(prev(inc) != current.begin())
inc--;
}
swap(current.front(), *inc++);
}
return move(res);
}
int main()
{
auto r = gen_matrix(6, 4);
for(auto v : r)
{
copy(v.begin(), v.end(), ostream_iterator<int>(cout, ", "));
cout << endl;
}
}
Note : The generation is made in reverse compared to your example, because this way is much more natural when using C++ containers (because of the iterator comparison with container end()). Also the boost part is used to pre-compute size and throw an exception early-on to avoid memory depletion (and reserve memory to avoid reallocations). This is not mandatory, you can as well comment this part out (at your own risks ^^).
The generator way
But you may need a generator, like if you're coding a program that will write Tera-octets of integer lists in big files saved on Peta-disks (well, who knows ?). Or you may want to be able to compute on n=100, r=80, skip 2 or 3 millions of vectors and then pick a bunch of them. Or you just want to avoid heavy memory usage. Well, anyway, a generator might come in handy; here it is.
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <stdexcept>
#include <boost/math/special_functions/binomial.hpp>
#include <boost/numeric/conversion/cast.hpp>
struct sum_list_generator
{
typedef vector<unsigned int> result_type;
sum_list_generator(unsigned int n, unsigned int r):
current(r, 0),
inc(current.begin())
{
if(inc != current.end()) *inc++ = n;
}
result_type operator()()
{
if(inc == current.end())
throw out_of_range("end of iteration");
result_type res = current;
if(current.front() == 0)
swap(current.front(), *inc++);
if(inc != current.end())
{
(*inc)++;
current.front()--;
if(current.front() != 0)
while(prev(inc) != current.begin())
inc--;
}
return move(res);
}
// helper function : number of outputed vectors
static size_t count(unsigned int n, unsigned int r)
{
return boost::numeric_cast<size_t>(
boost::math::binomial_coefficient<double>(n + r - 1, r - 1)
);
}
private:
result_type current;
result_type::iterator inc;
};
int main()
{
sum_list_generator g(6, 4);
try
{
while(true)
{
auto v = g();
copy(v.begin(), v.end(), ostream_iterator<int>(cout, ", "));
cout << endl;
}
}
catch(out_of_range const&) {}
}
Note: Again the count member function can be erased. Also, you usually avoid to throw an exception on an expected execution path in C++ (as opposed to python). Here the generator can be used to fill some other structure and, if your parameters are well-chosen, it will not throw. If you try to use it too much, of course it throws an out-of-range. Ultimately, catching the exception and silencing it like here in the main is very bad design - this is just an example you can use to try some fun parameters like (100, 80). The count() function gives you exact boundaries if you need a full list of vectors : use it.
