Génération de tuples index modulo

Question

Je cherche un algorithme (ou une implémentation de type C, pas d'outils disponibles) qui génère tous les tuples [a_0 a_1 ... a_ (n-1)] tel que 0 < = a_i < = i + 1. Les pointeurs vers la littérature sont également les bienvenus.

Answer 1

quelque chose comme ça?

void printTuples (int n, int[] a, int i=0) { 
    if (i == n) { 
     //print a 
     return; 
    } 
    for (int j=0; j<=i+1; j++) { 
     a[i] = j; 
     printTuples (n, a, i+1); 
    } 
} 

Answer 2

Cela s'appelle backtracking. Recherche wikipedia à ce sujet. Vous pouvez le faire à la fois récursif ou itératif. Amir, il veut entre 0 et i + 1, pas entre 0 et i. Et je pense que les tableaux de passes sur la pile sont plus lents que de les voir comme globaux.

Je pense que vous voulez quelque chose comme ceci:

int a[YOUR_LENGTH]; 

void backtracking (int n, int counter) { 
    if (counter == n) { 
     // do whatever 
     return; 
    } 
    for (int j = 0; j <= counter + 1; ++ j) { 
     a[counter] = j; 
     backtracking(n, counter + 1); 
    } 
}