c++ - 将递归 Python 列表生成器转换为 C++

Question

出于速度目的，我需要转换这段Python代码。 r 和 n 是用户定义的整数变量。

该函数应该生成符合以下条件的所有列表:

listSum = n，长度 = r，值(带替换)位于 [0,1,2,...,n] 中

def recurse(r,n):
    if r == 1:
        yield [n]
        return
    for i in range(n+1):
        for j in recurse(r-1,n-i):
            yield [i]+j

我尝试使用静态变量，但它们在错误的时间递增。我尝试从主函数更改我需要的变量(r、n 和 i)，并将它们传递给我的生成器等效函数，但此解决方案似乎不适用于 r 和 n 的不同初始值。我正在使用没有安装 Boost 的系统，并且我没有安装它的系统权限。那么如何将递归 python 列表生成器转换为 C++ 呢？

当我迭代recurse(r=3, n=4)时，我得到:

[0, 0, 4]
[0, 1, 3]
[0, 2, 2]
[0, 3, 1]
[0, 4, 0]
[1, 0, 3]
[1, 1, 2]
[1, 2, 1]
[1, 3, 0]
[2, 0, 2]
[2, 1, 1]
[2, 2, 0]
[3, 0, 1]
[3, 1, 0]
[4, 0, 0]

Answer 1

首先，您可以查看this thread有关您的算法的更多信息。你会发现你生成的列表数量是 (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++ 容器时这种方式更加自然(因为迭代器与容器 < em>end())。此外，boost 部分用于预先计算大小并尽早抛出异常以避免内存耗尽(并保留内存以避免重新分配)。这不是强制性的，您也可以将此部分注释掉(风险自负^^)。

生成器方式

但是您可能需要一个生成器，就像您正在编写一个程序，该程序将在保存在 Peta 磁盘上的大文件中写入 Tera 八位字节的整数列表(好吧，谁知道呢？)。或者您可能希望能够计算 n=100、r=80、跳过 2 或 3 百万个 vector ，然后选择其中的一堆。或者您只是想避免大量内存使用。好吧，无论如何，发电机可能会派上用场；就是这里。

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

注意:同样可以删除计数成员函数。此外，您通常会避免在 C++(而不是 python)中的预期执行路径上引发异常。这里的生成器可以用来填充一些其他结构，如果你的参数选择得当，它就不会抛出异常。如果您尝试过多地使用它，当然它会抛出超出范围。最终，像这里这样在 main 中捕获异常并使其静音是非常糟糕的设计 - 这只是一个示例，您可以使用它来尝试一些有趣的参数，例如 (100, 80)。如果您需要完整的 vector 列表，count() 函数可以为您提供精确的边界:使用它。