# How to iterate through all values of an array?

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).

• This is such a low-level algorithm that, to me, it's just a programming question. Hint: treat the array as a SIZE-digit number written in base-MAX. – David Richerby Feb 10 '16 at 18:03
• Meta question about the closure of this question Cc @DavidRicherby – Gilles 'SO- stop being evil' Feb 11 '16 at 10:37
• Thanks for concentrating on one question and explicitly stating the availability of MAX and SIZE. – greybeard Feb 11 '16 at 23:34

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.

• The "direct iteration" is exactly what I was looking for. All I need to do is to implement a method next() that increases the array in that lexicographic order, then loop until the array doesn't "hasNext". When I asked, the problem appeared too difficult for me, but after you answered, it looks trivial now :) Thank you. – qsp Feb 12 '16 at 2:02
• "Treat as an integer" is a clever hack, but converting to integer is not practical with large values of SIZE and RANGE. – qsp Feb 12 '16 at 2:05