C++中的递归生成器

Question

我有一个size = N的向量,其中每个元素我可以有从0到possible_values [i] -1的值.我想做一个函数,迭代我所有这些值.

我能够使用递归生成器在Python中执行此操作:

def all_values(size,values,pos=0):
    if pos == size:
        yield []
    else:    
        for v in xrange(values[pos]):
            for v2 in all_values(size,values,pos+1):
                v2.insert(0,v)
                yield v2

possible_values=[3,2,2]
for v in all_values(3,possible_values):
    print v

示例输出:

[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]
[2, 0, 0]
[2, 0, 1]
[2, 1, 0]
[2, 1, 1]

由于C++没有Python的产量,我不知道在C++中实现它的正确方法是什么.

可选问题:有没有更好的方法在Python中实现它？

Answer 1

这个问题让我想起了一些奇怪的混合模算术数。

我用 Python 组合了一些东西。您应该能够在 C++ 中轻松地重新实现它。我有时使用输入流运算符operator>>(...)来实现类似 C++ 生成器的东西（惰性求值是 Python 生成器的一个非常好的功能）。否则它只是一个存储状态的对象，让您在需要时获取下一个值。

这是一些示例代码：

class Digit:
    def __init__(self, modulus):
        self.modulus = modulus
        self.value = 0
    def __str__(self):
        return str(self.value)
    def __nonzero__(self):
        return bool(self.value)
    def increment(self):
        self.value += 1
        self.value %= self.modulus
        return self.value == 0

class Number:
    def __init__(self, moduli):
        self.digits = [Digit(m) for m in moduli]
    def __str__(self):
        return "".join(str(d) for d in self.digits)
    def __nonzero__(self):
        return any(d for d in self.digits)
    def increment(self):
        carryover = True
        for d in reversed(self.digits):
            if carryover:
                carryover = d.increment()

n = Number([3,2,2])
while True:
    print n
    n.increment()
    if not n:
        break

这是输出：

000
001
010
011
100
101
110
111
200
201
210
211

一些进一步参考的链接：

• 运算符重载
• 自定义类似流的类

我在 C++ 中设置了一个示例：

#include <sstream>
#include <string>
#include <iostream>
#include <vector>

struct number {
    struct digit {
        int value;
        int modulus;
        digit(int modulus) : value(0), modulus(modulus) {}
        bool increment() {
            value = (value+1)%modulus;
            return !value;
        }
        operator void*() {
            return value ? this : 0;
        }
        std::string to_str() {
            return std::to_string(value);
        }
    };
    std::vector<digit> digits;

    number(std::vector<int> const & moduli) {
        for (auto i : moduli)
            digits.push_back(digit(i));
    }

    void increment() {
        bool carry = true;
        for (auto d = digits.rbegin(); d != digits.rend(); d++)
            if (carry)
                carry = d->increment();
    }

    operator void*() {
        for (digit & d : digits)
            if (d) return this;
        return 0;
    }

    std::string to_str() {
        std::stringstream o;
        for (auto & d : digits)
            o << d.to_str();
        return o.str();
    }
};

int main() {
    number n({3,2,2});
    for(;;) { 
        std::cout << n.to_str() << '\n';
        n.increment();
        if (!n) break;
    }
}

输出示例：

$ g++ test.cc -std=c++11 && ./a.out
000
001
010
011
100
101
110
111
200
201
210
211