python - C++ 中的递归生成器

Question

我有一个大小为 N 的 vector ，其中每个元素 i 的值可以从 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 的 yield，我不知道在 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

---

一些供进一步引用的链接:

• Operator overloading
• Custom stream-like classes

---

我已经用 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