How to iterate through all values of an array?

Question

I'm trying to implement a brute-force algorithm.

If I have one variable x, I can iterate through all its values using a for loop:

for x in {1,2,..,MAX}:
    do something with x

But what if I have an array A? The array has length SIZE, and each element takes values in the range 1..MAX. Thus, there are MAX^SIZE possible values of this array. How do I iterate through all such possible values?

I'm asking for an algorithm, not an implementation on a particular language. Both MAX and SIZE are arguments. SIZE is not fixed, so I can't just create a set of nested for-loops (the number of for-loops that would be needed isn't fixed in advance and depends on the value of SIZE).

Answer 1

There are several approaches. I will use 0-based indexing (so array elements are in the range 0 .. MAX-1) rather than 1-based indexing (range 1 .. MAX), for ease of notation.

Treat as an integer

You can treat the contents of an array as an integer in the range 0 .. MAX^SIZE - 1, expressed in base MAX. For example, the array with contents [0, 3, 1] corresponds to the integer 0 * MAX^2 + 3 * MAX + 1. Conversely, each such integer corresponds to an array.

Of course you can iterate through these integers by starting at 0 and incrementing until you reach MAX^SIZE - 1. Now by expressing that integer in base MAX, you can convert the integer to an array, and thereby iterate through all possible values of the array.

Depth-first search

You can view this as a complete tree of depth SIZE, where each internal node has branching factor MAX. Each leaf of the tree corresponds to a value of the array. Then, you can iterate through the leaves of the tree following any standard tree traversal algorithm.

Direct iteration

To iterate through these arrays, it suffices to create an order on the arrays and build an algorithm to advance from one array to the next-largest array. For this, you can use lexicographic order. The smallest (first) such array is the all-zeros array [0, 0, ..., 0].

Given an array A, you can advance to the next array in lexicographic order via a simple procedure. Basically, you increment the last element of the array; if that becomes too large (equal to MAX), it wraps around to 0, and then you increment the next-to-last element of the array (continuing if it wraps around). If you think about it a bit, this is basically equivalent to the "treat as an integer" solution.

Running time

All of these methods have basically the same running time. Asymptotically they all require approximately MAX^SIZE operations. Depending on representation and implementation details, direct iteration might be slightly faster, but the differences are likely to be minor.

(The fine print: depending upon implementation details, the running time of the "treat as an integer" method might be more like SIZE * MAX^SIZE.)

There's no algorithm that can iterate through all values of the array in less than MAX^SIZE operations (as the number of possible arrays is a lower bound on the time to iterate through them all), so there's no hope for an algorithm that is significantly better.