递归生成器在C ++ [英] Recursive generator in C++

问题描述

我有一个大小= N的向量，其中每个元素i可以具有从0到possible_values [i] -1的值。我想用一个函数来遍历所有这些值。

I have a vector of size = N where each element i can have values from 0 to possible_values[i]-1. I want to do a function that iterates me through all those values.

我可以在Python中使用递归生成器：

I was able to do that in Python using a recursive generator:

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 ++中实现这个的正确方法。

Since C++ doesn't have the Python's yield I don't know what is the right way to implement this in C++.

可选问题：

Optional Question: Is there a better way to implement this in Python?

推荐答案

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

This problem reminded me of some strange mixed-modulus arithmetic numbers.

我在Python中放在一起。你应该能够轻松地在C ++中重新实现这一点。我有时使用输入流运算符 operator>>（...），以便在C ++中实现像一个生成器（延迟评估是Python的生成器）。

I've put something together in Python. You should be able to reimplement this easily in C++. I sometimes used the input stream operator operator>>(...) in order to implement something like a generator in C++ (lazy evaluation is a really nice feature of Python's generators). Otherwise it'd be just an object that stores the state and let's you get the next value when you need it.

这里是一些示例代码：

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

---

有些链接供进一步参考：

---

Some links for further reference:

• 操作员重载


• 自定义类流类

• Operator overloading
• Custom stream-like classes

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

I've set up an example in 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

这篇关于递归生成器在C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！