Algorithm for iterating over a space of numbers

Question

I hope this is not a hoax, but it’s hard to reduce the problem to keywords!

This is always what I was thinking. Say you have a black box that takes n integers as input (where n> 1). Given that there are restrictions on integer values, how would you start writing an algorithm that will push out the entire sample space through a black box? (bonus points if n can be indicated 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 suitable for two variables, but as you might have guessed, my algorithm gets very ugly when n approaches double-digit numbers.

Is there a better way to do this than nesting if statements like I made?

I know a bad way to do this, that it would randomly generate values ​​for each iteration and save the inputs of previous iterations so that you don't poke a black box with the same variables twice. However, I was hoping for a faster method, since the collision really damaged the runtime, since the number of unique black box calls (max - min + 1) ^ n

Answer 1

Why aren't nested loops used? Then you simply add more nested loops as needed.

You cannot be too efficient, but you indicated that you need to cover the entire sample space, so you will have to run every possible combination of input variable values ​​in the future, so I doubt that you can do much if it cannot only evaluate part 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 ); 

In addition, I think you will find the number of unique calls (max - min + 1) ^ n , and not vice versa.

Edit:

Different runtime version for already proposed

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

Here's the real-time version of Python, in each case x will be an n-tuple, for example [1,0,3,2] . The only thing I will say is that it does not include max in the state space (in the example below it will use from 0 to 2 inclusive, and not 3), so before using it you will need to increase max .

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

Answer 2

The numbers will be stored in the array a , which will be set dynamically, for example: int a[] = new int[n]

If the blackBox parameter cannot be changed to take a sample as an array, you can either write an ugly wrapper function to call it with a different number of parameters, or you are just out of luck if you do it dynamically.

(Procedural) Pseudocode:

 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]++; } } 

Answer 3

Here is a general 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 gets the maximum values ​​for each position. The minimum is always 0 (so you can use it to simulate a counter in any radius and in any "mixed radius"). I have added a usage example below.

Answer 4

You can represent each black box entry as n -digit number in the max - min + 1 radix system . For example, if min = 3 and max = 12 , then max - min + 1 == 10 , and each black box entry corresponds to an n-digit number in the decimal system. Just iterate over all numbers from 0 to (max - min + 1)^n , decode each number and submit the resulting vector to the black box.

Here's the Java implementation:

 public static interface BlackBox { void consume(int... vector); } public static void iterateSample(int min, int max, int n, BlackBox bb) { int radix = max - min + 1; long limit = (long) Math.pow(radix, n); /* Imprecise for larger numbers! */ for (int i = 0; i < limit; i++) { int encoded = i; int[] decoded = new int[n]; for (int j = 0; j < n; j++) { decoded[j] = min + (encoded % radix); encoded /= radix; } bb.consume(decoded); } }