Recursive generator in C++

Question

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.

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

Example output:

[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]

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?

Answer 1

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

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.

Here's some example code:

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

Here's the output:

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

---

Some links for further reference:

• Operator overloading
• Custom stream-like classes

---

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;
    }
}

Example output:

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