Algorithme pour itérer à travers l'espace échantillon de nombres

Question

J'espère que ce n'est pas une dupe, mais il est difficile de résumer le problème en mots-clés!

C'est toujours quelque chose que je me suis demandé. Disons que vous avez une boîte noire qui prend n entiers comme une entrée (où n> 1). Étant donné qu'il y a une limite sur les valeurs entières, comment allez-vous écrire un algorithme qui va pousser tout l'espace d'échantillon à travers la boîte noire? (Points de bonus si n peut être spécifié lors de l'exécution)

Ma tentative quand n = 2 est la suivante:

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

Le code ci-dessus est très bien pour deux variables, mais comme vous pouvez le deviner, mon algorithme devient vraiment moche quand n approches à deux chiffres.

Existe-t-il une meilleure façon de procéder que d'imbriquer des instructions comme celles que j'ai faites?

Je connais un mauvais moyen de le faire, qui serait de générer aléatoirement les valeurs pour chaque itération et enregistrer les entrées des itérations précédentes afin de ne pas pointer deux fois la boîte noire avec les mêmes variables. Cependant, j'espérais une méthode plus rapide que les collisions blessent vraiment le temps d'exécution que le nombre de boîte noire unique, appelle des approches (max - min + 1)^n

Answer 1

Pourquoi ne sont pas utilisés boucles imbriquées? Ensuite, vous ajoutez simplement d'autres boucles imbriquées si nécessaire.

peut-être pas trop efficent mais vous avez-vous indiqué besoin pour couvrir tout l'espaceexemple, vous allez devoir exécuter toutes les combinaisons possibles de valeurs des variables d'entrée anway - donc je doute qu'il y ait beaucoup plus que vous peut faire à propos de l'efficacité, à moins qu'il soit possible de seulement évaluer contre une partie de l'espace d'état.

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

En outre, je pense que vous trouverez le nombre d'appels uniques est (max - min + 1)^n, et non l'inverse.

Edit:

Une autre version d'exécution à celui déjà proposé

Imre L semble avoir frappé le clou sur la tête pour une version en temps réel en utilisant le même type de langue comme votre question (quelque chose comme un C), mais puisque vous avez étiqueté cela comme agnostique de langue, j'ai décidé d'essayer quelque chose de différent (aussi, j'apprends Python en ce moment cherchait donc une excuse pour pratiquer).

Voici une version en temps réel Python, dans chaque cas, x sera un n-uplet, tel que [1,0,3,2]. La seule chose que je dirai est ceci pas inclure max dans l'espace d'état (dans l'exemple ci-dessous il utilisera 0 à 2 inclus, pas 3) de sorte que vous auriez à incrémenter max avant utilisation.

import itertools 

min = 0 
max = 3 
n = 4 

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

Answer 2

Voici une solution générique, 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())); 
     } 
    } 
} 

Le constructeur reçoit les valeurs maximales pour chaque position. Le minimum est toujours 0 (donc vous pouvez l'utiliser pour simuler un compteur dans n'importe quelle base, et dans n'importe quelle "base mixte"). J'ai ajouté un exemple d'utilisation en bas.

Answer 3

Les numéros auront lieu dans le tableau a qui seront définis de manière dynamique par exemple: int a[] = new int[n]

Si le blackBox ne peut pas être modifié pour prendre un échantillon sous forme de tableau, vous pouvez écrire une fonction d'emballage laid pour appeler avec différents nombre de paramètres ou vous n'avez pas beaucoup de chance de le faire dynamiquement.

code (procédure) 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

Vous pouvez penser de chaque entrée de la boîte noire comme un n nombre à chiffres dans un système max - min + 1radix. Par exemple, si min = 3 et max = 12, alors max - min + 1 == 10 et chaque entrée dans la boîte noire correspond à un nombre à n chiffres dans le système décimal. Il suffit de parcourir tous les nombres de 0 à (max - min + 1)^n, de décoder chaque nombre et de transmettre le vecteur résultant à la boîte noire.

Voici une implémentation 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); 
    } 
}