Algorithm to iterate through sample space of numbers

Question

I hope this isn't a dupe, but it's hard to boil down the problem into keywords!

This is always something that I've wondered about. Let's say you have a black box that takes n integers as an input (where n > 1). Given that there is a bounds on the integer values, how would you go about writing an algorithm that will push the entire sample space through the black box? (bonus points if n can be specified at runtime)

My attempt when n = 2 is as follows:

int min = 0;
int max = 9;
int a = min;
int b = min;

while(a <= max && b <= max)
{
  blackBox(a, b);
  a++;
  if(a > max)
  {
    a = min;
    b++;
  }
}

The above code is fine for two variables, but as you might guess, my algorithm gets really ugly when n approaches double-digits.

Is there a better way to do this other than nesting if statements like I have done?

I know a bad way to do it, which would be to randomly generate the values for each iteration and save the inputs of previous iterations so you don't poke the black box with the same variables twice. However, I was hoping for a more speedy method as collisions really hurt the execution time as the number of unique black box calls approaches (max - min + 1) ^ n

Answer 1

Why not used nested loops? Then you just add more nested loops as necessary.

Might not be overly efficent but you did indicate you need to cover the entire sample space, so you're going to have to run every possible combination of values of the input variables anway - so I doubt there's much you can do about efficency unless it's possible to only evaluate against a portion of the state space.

int min = 0;
int max = 9;
for( int a = min ; a <= max ; ++a )
    for( int b = min ; b <= max ; ++b )
        blackBox( a , b );

Also, I think you'll find the number of unique calls is (max - min + 1) ^ n, not the other way around.

Edit:

A different run-time version to that already suggested

Imre L seems to have hit the nail on the head for a real-time version using the same language type as your question (something C-like), but since you've tagged this as language agnostic I've decided to try something different (also, I'm learning Python at the moment so was looking for an excuse to practice).

Here's a Python real-time version, in each case x will be a n-tuple, such as [1,0,3,2]. Only thing I will say is this does not include max in the state-space (in the example below it will use 0 to 2 inclusive, not 3) so you'd have to increment max before use.

import itertools 

min = 0
max = 3
n = 4

for x in itertools.product(range(min,max), repeat=n):
        blackBox( x )

Answer 2

Here is a generic solution, in Java:

public class Counter implements Iterator<int[]> {
    private int[] max;
    private int[] vector;

    public Counter(int[] maxValues) {
        this.max = maxValues;
        this.vector = new int[maxValues.length];
    }

    public int[] next() {
        if (!hasNext())
            throw new NoSuchElementException();

        int[] res = vector.clone();
        int i = 0;
        while (i < vector.length && vector[i] == max[i]) {
            vector[i] = 0;
            i++;
        }
        if (i == vector.length)
            vector = null;
        else
            vector[i]++;

        return res;
    }

    @Override
    public boolean hasNext() {      
        return (vector != null);
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();      
    }

    public static void main(String[] args) {
        Counter c = new Counter(new int[]{3});
        while (c.hasNext()) {
            System.out.println(Arrays.toString(c.next()));
        }
    }
}

The constructor receives the maximum values for each position. The minimum is always 0 (therefore you can use it to simulate a counter in any radix, and in any "mixed radix"). I added a usage example at the bottom.

Answer 3

The numbers will be held in array a that will be set dynamically eg: int a[] = new int[n]

If the blackBox cannot be modified to take a sample as array then you can either write an ugly wrapper function for calling it with different count of parameters or you are pretty much out of luck for doing it dynamically.

(Procedural) Pseudo code:

int min = 0;
int max = 9;
int a[] = array();
int count = length(a);

setToMinValue(a);

while(a[count-1] <= max)
{ 
  blackBox(a); // or bb(a[0],a[1],...)
  a[0]++;
  //while next number needs to be increased
  for (int i = 0; a[i] > max && i < count-1; i++) {
    a[i] = min;
    a[i+1]++;
  }
}