Algoritmo per iterare attraverso lo spazio campione dei numeri

Question

Spero che questo non sia un capriccio, ma è difficile riassumere il problema in parole chiave!

Questo è sempre qualcosa che mi sono chiesto. Supponiamo che tu abbia una casella nera che accetta n come input (dove n> 1). Dato che c'è un limite sui valori interi, come andresti a scrivere un algoritmo che spingerà l'intero spazio campione attraverso la scatola nera? (Punti bonus se n possono essere specificati in fase di esecuzione)

Il mio tentativo quando n = 2 è la seguente:

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

Il codice di cui sopra è bene per due variabili, ma come si può immaginare, il mio l'algoritmo diventa davvero brutto quando n si avvicina alle doppie cifre.

C'è un modo migliore per fare questo diverso dal nidificare se le affermazioni come ho fatto?

Conosco un modo non corretto di farlo, che sarebbe generare casualmente i valori per ciascuna iterazione e salvare gli input delle iterazioni precedenti in modo da non attirare la scatola nera con le stesse variabili due volte. Tuttavia, speravo in un metodo più veloce in quanto le collisioni danneggiavano davvero il tempo di esecuzione poiché il numero di chiamate nere uniche si avvicina a (max - min + 1)^n

Answer 1

Perché non utilizzare cicli annidati? Quindi basta aggiungere altri cicli annidati, se necessario.

potrebbe non essere troppo efficiente, ma si ha indicato il necessario per coprire lo spazio campione intero, così si sta andando ad avere per eseguire ogni possibile combinazione di valori delle variabili di input Anway - quindi dubito c'è molto che si può fare circa l'efficacia a meno che non sia possibile valutare solo contro una porzione dello spazio dello stato.

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

Inoltre, penso che troverete il numero di chiamate uniche è (max - min + 1)^n, non il contrario.

Edit:

Una diversa versione di runtime a quello già suggerito

Imre L sembra aver colpito il chiodo sulla testa per una versione in tempo reale utilizzando lo stesso tipo di lingua come la tua domanda (qualcosa di simile a C), ma dal momento che hai taggato questo come agnostico del linguaggio ho deciso di provare qualcosa di diverso (inoltre, sto imparando Python al momento, quindi cercavo una scusa per esercitarmi).

Ecco una versione in tempo reale Python, in ogni caso x sarà una n-tupla, ad esempio [1,0,3,2]. L'unica cosa che dirò è che questo non include max nello spazio di stato (nell'esempio seguente utilizzerà 0-2 compreso, non 3) quindi dovresti incrementare max prima dell'uso.

import itertools 

min = 0 
max = 3 
n = 4 

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

Answer 2

Ecco una soluzione generica, 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())); 
     } 
    } 
} 

Il costruttore riceve i valori massimi per ciascuna posizione. Il minimo è sempre 0 (quindi puoi usarlo per simulare un contatore in qualsiasi radix e in qualsiasi "mixed mix"). Ho aggiunto un esempio di utilizzo in basso.

Answer 3

I numeri si terrà a matrice a che sarà impostato in modo dinamico ad esempio: int a[] = new int[n]

Se il blackBox non può essere modificato per prendere un campione come array di allora si può scrivere una funzione wrapper brutto per la chiamata con diversi il conteggio dei parametri o sei piuttosto sfortunato per averlo fatto dinamicamente.

codice (procedurale) 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

Si può pensare di ogni ingresso alla scatola nera, come un numero di digit n in un sistema max - min + 1radix. Ad esempio, se min = 3 e max = 12, quindi max - min + 1 == 10 e ciascun ingresso nella casella nera corrisponde a un numero di n cifre nel sistema decimale. Basta scorrere tutti i numeri da 0 a (max - min + 1)^n, decodificare ogni numero e alimentare il vettore risultante nella casella nera.

Ecco un'implementazione 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); 
    } 
}