Generating tuples modulo index

Question

I am looking for an algorithm (or a C-like implementation, no itertools available) which generates all tuples [a_0 a_1 ... a_(n-1)] such that 0 <= a_i <= i + 1. Pointers to literature are also welcome.

Answer 1

something like this?

void printTuples (int n, int[] a, int i=0) {
    if (i == n) {
        //print a
        return;
    }
    for (int j=0; j<=i+1; j++) {
        a[i] = j;
        printTuples (n, a, i+1);
    }
}

Answer 2

It's called backtracking. Search wikipedia about it. You can do it both recursive or iterative.

Amir, he wants between 0 and i + 1, not between 0 and i. And i think passing arrays on the stack is slower thant accesing them as global.

I think you want something like this:

int a[YOUR_LENGTH];

void backtracking (int n, int counter) {
    if (counter == n) {
        // do whatever
        return;
    }
    for (int j = 0; j <= counter + 1; ++ j) {
        a[counter] = j;
        backtracking(n, counter + 1);
    }
}