Algoritmo de repetición de espacio de muestra de números

Question

espero que esto no es una víctima, pero es difícil para hervir el problema en palabras clave!

Esto siempre es algo que me he preguntado. Digamos que usted tiene un cuadro negro que lleva n enteros como entrada (donde n > 1). Dado que hay límites en los valores enteros, ¿cómo harías para escribir un algoritmo que empujara todo el espacio de muestra a través del recuadro negro? (Puntos de bonificación si n se pueden especificar en tiempo de ejecución)

Mi intento cuando n = 2 es el siguiente:

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

El código anterior está muy bien para dos variables, pero como se puede imaginar, mi el algoritmo se vuelve realmente feo cuando n se acerca a los dígitos dobles.

¿Hay una mejor manera de hacer esto con excepción de anidación si declaraciones como lo he hecho?

Conozco una mala forma de hacerlo, que sería generar aleatoriamente los valores para cada iteración y guardar las entradas de las iteraciones anteriores para no golpear dos veces la caja negra con las mismas variables. Sin embargo, esperaba de un método más rápido que las colisiones daño de verdad el tiempo de ejecución como el número de cuadro negro única llama se acerca (max - min + 1)^n

Answer 1

bucles anidados ¿Por qué no se utilizan? Luego solo agrega más bucles anidados según sea necesario.

Puede que no sea excesivamente eficiente pero indicó que necesita para cubrir el espacio muestral toda, por lo que vamos a tener que correr todas las combinaciones posibles de los valores de las variables de entrada anway - por lo que duda hay mucho que puede hacer acerca de la eficiencia a menos que sea posible evaluar solo en contra de una porción del espacio de estado.

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

Además, creo que encontrará el número de llamadas únicas es (max - min + 1)^n, no al revés.

Editar:

Una versión de tiempo de ejecución diferente a la que ya se ha sugerido

Imre L parece haber dado en el clavo en la cabeza por una versión en tiempo real utilizando el mismo tipo de lenguaje como su pregunta (algo parecido a C), pero ya que este ha etiquetado como el lenguaje agnóstico he decidido probar algo diferente (también, estoy aprendiendo Python en el momento y estaba buscando una excusa para practicar).

Aquí está una versión de Python en tiempo real, en cada caso x será una n-tupla, como [1,0,3,2]. Lo único que puedo decir es que esto hace no incluyen max en el espacio de estado (en el ejemplo siguiente se utilice 0 a 2 inclusive, no 3) por lo que tendría que incrementar max antes de su uso.

import itertools 

min = 0 
max = 3 
n = 4 

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

Answer 2

Aquí es una solución genérica, en 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())); 
     } 
    } 
} 

El constructor recibe los valores máximos para cada posición. El mínimo es siempre 0 (por lo tanto, puede usarlo para simular un contador en cualquier raíz, y en cualquier "raíz mixta"). Agregué un ejemplo de uso en la parte inferior.

Answer 3

Los números se llevará a cabo en orden a que se establece dinámicamente por ejemplo: int a[] = new int[n]

Si el blackBox no puede ser modificado para tomar una muestra como una matriz entonces usted puede escribir una función de contenedor fea para llamar con diferentes cuenta de parámetros o no está de suerte para hacerlo de forma dinámica.

código (procesal) Pseudo:

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 4

Se puede pensar en cada entrada a la caja de negro como un número de dígitos n en un sistema max - min + 1radix. Por ejemplo, si min = 3 y max = 12, entonces max - min + 1 == 10 y cada entrada al recuadro negro corresponde a un número de n dígitos en el sistema decimal. Simplemente itere sobre todos los números desde 0 hasta (max - min + 1)^n, decodifique cada número y alimente el vector resultante al recuadro negro.

Aquí es una implementación de Java:

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); 
    } 
}