How to loop over all possible vectors of certain length in lexicographic order?

Question

Let's say we have a vector of length 4, where every element can be a number from 0 to 9. For example: <1, 8, 0, 3>

Instead of simply looping over all 10^4 possible vectors, I want to loop in an specific order. So I want to start from <0, 0, 0, 0>, go to <1, 0, 0, 0>, then:

<2, 0, 0, 0>, <3, 0, 0, 0>, ..., <9, 0, 0, 0>, <0, 1, 0, 0>

and so on (notice the order in the last two). I cannot think of a way to write this for variable vector length.

Let's say we are in the ith iteration, having the ith vector in the lexicographic order I mentioned above. Having the ith vector is necessary for doing some process in the (i+1)th vector. This scheme saves compute over randomly looping over all possible vectors.

I haven't really found a non-brute force and memory efficient way to solve this problem. Specially considering that I should be able to support variable vector lengths and different ranges of numbers for entries.

Answer 1

So in this case you can think of each element as a number in base 10. The i'th element is i in base 10 with the digits arranged in reverse order. For instance:

int[] indexToElement(int index, int base) {
    String string = Integer.toString(index, base);
    int[] element = new int[string.length()];

    for (int i = 0; i < string.length(); ++i) {
        element[i] = Character.digit(string.charAt(string.length() - i - 1), base);
    }

    return element;
}