Перевести рекурсивный генератор списков Python на C++

Во-первых, вы можете проверить эту тему для получения дополнительной информации о вашем алгоритме. Вы обнаружите, что количество сгенерированных вами списков равно (n+r-1)C(r-1), это может помочь. Есть несколько способов перевести этот код, но я дам вам два.

Итеративный способ

Во-первых, в C++ шаблон генератора не очень распространен. В зависимости от того, что вы хотите сделать, большую часть времени вы предпочитаете фактически выделять память для всего этого вывода в начале, вычислять дату, а затем возвращать полную матрицу. Во-вторых, вы не можете рекурсировать таким образом в C++, вы очень быстро испортите свой стек. Итак, вам нужна итеративная версия вашего алгоритма. Вот как это сделать (с итераторами, как нам нравится в 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;
    }
}

Примечание. Генерация производится в обратном порядке по сравнению с вашим примером, потому что этот способ гораздо более естественен при использовании контейнеров C++ (из-за сравнения итератора с контейнером end ()). Кроме того, часть boost используется для предварительного вычисления размера и раннего создания исключения, чтобы избежать истощения памяти (и резервирования памяти, чтобы избежать перераспределения). Это не обязательно, вы также можете закомментировать эту часть (на свой страх и риск ^^).

Способ генератора

Но вам может понадобиться генератор, например, если вы пишете программу, которая будет записывать Тера-октеты целочисленных списков в большие файлы, сохраненные на пета-дисках (ну кто знает?). Или вы можете захотеть вычислить n = 100, r = 80, пропустить 2 или 3 миллиона векторов и затем выбрать несколько из них. Или вы просто хотите избежать интенсивного использования памяти. Ну, во всяком случае, генератор может пригодиться; вот.

#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&) {}
}

Примечание. Функция-член count снова может быть удалена. Кроме того, вы обычно избегаете генерировать исключение на ожидаемом пути выполнения в C++ (в отличие от python). Здесь генератор можно использовать для заполнения какой-то другой структуры и при удачном подборе параметров он не кинет. Если вы попытаетесь использовать его слишком часто, он, конечно же, выдаст выход за пределы допустимого диапазона. В конечном счете, перехватывать исключение и заглушать его, как здесь, в main — очень плохой дизайн — это просто пример, который вы можете использовать, чтобы попробовать некоторые забавные параметры, такие как (100, 80). Функция count() дает вам точные границы, если вам нужен полный список векторов: используйте ее.

Функции обратного вызова часто хорошо работают как итераторы:

#include <functional>
#include <iostream>

// manipulates the memory at `dest`, and calls `doNext()` each time it contains a new set of data
void recurseHelper(int r, int n, std::function<void()> doNext, int* dest) {    
    if(r == 1) {
        *dest = n;
        doNext();
    }
    else for(int i = 0; i <= n; i++) {
        *dest = i; 
        recurseHelper(r-1, n-i, doNext, dest + 1);
    }
}

void recurse(int r, int n, std::function<void(int*)> f) {
    int dest[r];
    recurseHelper(r, n, [&] () {
        f(dest);
    }, dest);
}

int main() {
    recurse(3, 4, [] (int* i) {
        std::cout << i[0] << i[1] << i[2] << std::endl;
    });
    return 0;
}