Optimiser un code de combinaison pour toutes les longeurs de mots de 1 à 12 caractères

Pour y aller de manière itérative, c'est le même principe que le code récursif : la boucle extérieure itère sur le numéro du caractère qui sera ajouté, la boucle intérieure sur tous les caractères potentiels, une troisième boucle sur tous les mots de longueur inférieure, où on génère enfin un nouveau mot. En pseudo-Python (non testé, donc), la troisième boucle correspondant à une compréhension de liste :

Code:

---

1 2 3 4

generated = [[""]] for i in range(1, 12): for c in 'a' upto 'z': generated[i] = [w + c for w in generated[i - 1]]

---

Maintenant, si tu veux le code le plus rapide pour générer ces séquences de longueur constante, le mieux est probablement d'écrire explicitement tes douze boucles, puis de laisser le compilateur faire son travail (le code sera nettement plus simple, pas d'histoire d'accumulateur ou que sais-je, ses heuristiques d'optimisation pourront fonctionner à plein).

Transcris ce code C testé (qui est celui que j'avais donné en pseudo code)
Attention en C on commence les tableaux à 0.
Ne fonctionne pas si len est plus grand que 256.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

void toutes_les_combinaisons(char *ch, int len) { char nch[256] = {0}; int ind[256] = {0}; int lench = strlen(ch);   for(int i = 0; i < len; i++) nch[i] = ch[0];   int i = len-1; while(i >= 0) { puts(nch); ind[i]++; while (i >= 0 && ind[i] >= lench) { ind[i] = 0; nch[i] = ch[ind[i]]; i--; if (i >= 0) ind[i]++; } if (i >= 0) { nch[i] = ch[ind[i]]; i = len-1; } } }

---

Citation:

---

Envoyé par toni___

Quelqu'un aurait-il un code propre sans récursivité testé et qui fonctionne bien ?

---

toujours dans la même discussion

Citation:

---

Envoyé par toni___

Quelqu'un aurait-il un code propre sans récursivité testé et qui fonctionne bien ?

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

int ALPHABET_LENGTH = 3; char[] alphabet = {'a','b','c'};   int WORD_LENGTH = 6; char[] word = new char[WORD_LENGTH];   int N = (int)Math.pow(ALPHABET_LENGTH, WORD_LENGTH); for(int i=0; i<N; i++) {   for(int j=0,value=i; j<WORD_LENGTH; j++,value/=ALPHABET_LENGTH) word[j] = alphabet[ value % ALPHABET_LENGTH ];   // your code here... }

---

L'idée c'est simplement d'énumérer les valeurs de 1 à N, puis d'écrire cette valeur en base A (A = taille de l'alphabet) sur W chiffres (W = taille du mot).

En fait ce n'est calculable, car les combinaisons me serve à essayer de retrouver mon mot de passe perdu, d'une application que j'ai créé en MS Access.

C'est parfaitement calculable.
Nombre de caractères 'utilisables' dans un mot de passe : à toi de dire, disons 70.
Nombre de mots de passe possibles, avec une longueur de 1 caractère : N1=70
Nombre de mots de passe possibles, avec une longueur de 2 caractères : N2=70*70
Nombre de mots de passe possibles, avec une longueur de 3 caractères : N3=70*70*70

Nombre de mots de passe possibles, avec une longueur de 12 caractères : N12=70*70*70*70*70*70*70*70*70*70*70*70
Cumul = N1+N2+N3 ...+N12

Malheureusement (ou plutôt heureusement), ce nombre est très grand. Si tu peux tester 1000 combinaisons par secondes, il va te falloir plusieurs années pour tester toutes les combinaisons possibles.
Si tu sais que les derniers caractères, c'est soit ton prénom, soit ton nom, et qu'il faut chercher uniquement les 5 ou 6 caractères restants, tu réduis nettement le nombre de combinaisons, tu le divises par quelques millions.


Récursivité ou pas, ce n'est pas la question. La question, c'est que tester quelques milliards de milliards de combinaisons, c'est long.

Bonjour,
Merci pour ta réponse.

J'ai une idée de la combinaison à trouver :
sa longeur est entre 8 et 12 caractères et le champ des possibilités du vecteur de départ, j'ai pu le réduire à 24 caractères au lieu de 104.

Donc cela fait encore beaucoup de combinaisons.

Citation:

---

Envoyé par tbc92

Si tu peux tester 1000 combinaisons par secondes, il va te falloir plusieurs années pour tester toutes les combinaisons possibles.

---

Je peux tester 278 combinaisons /seconde, ce n'est pas assez rapide !

pour tester le password à ma db j'utilise la ligne de code suivante :
Set db = acc.DBEngine.OpenDatabase(strDbName, False, False, ";PWD=" & strPassword)

qui je pense est une méthode DAO ?

Peut-être je dois trouver une autre façon de faire que cette ligne de code pour gagner en rapidité d'exécution ?

Merci à chacun d'entre vous
pour vos exemples de codes avec ou sans récursivité.

Citation:

---

Envoyé par toni___

Peut-être je dois trouver une autre façon de faire que cette ligne de code pour gagner en rapidité d'exécution ?

---

Oui, très clairement : générer des combinaisons ne sera pas un facteur limitant (c'est extrêmement rapide si tu ne fais qu'itérer sur toutes les lettres pour une longueur donnée). Pour ça, demande plutôt sur un forum orienté bases de données… (Réfléchis aussi à du parallélisme.)

Bonjour,

Voici un petit code R qui affiche le ou les n-ièmes mots en utilisant l'alphabet fourni.
L'idée est de convertir le nombre n dans une base b où b est le nombre de lettres de l'alphabet.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

GetWords <- function(n, k, alphabet = c('a', 'b')) { ## Get the n-nth words with k letters using a given alphabet. stopifnot( n >= 0, length(k) == 1, k > 0, length(alphabet) > 0) m <- length(alphabet); ## Get a single word GetWord <- function(x) { ## Create an empty word filled with '0' word <- rep(alphabet[1], k) i <- k ## Convert the number 'x' to base 'm' while(x > 0) { word[i] <- alphabet[(x %% m)+1] i <- i - 1; x <- x %/% m } return(paste(word, collapse ='')) } ## Get all words (vectorized loop) sapply(n, GetWord) }   ## Convert to binary GetWords(1:10, k=4) ## Convert to decimal GetWords(5:10, k=4, alphabet=0:9)

---

Je ne connais pas VBA, mais il ne devrait pas y avoir de problème particulier pour traduire le code.

Ce code plus général sera efficace, mais il peut être optimisé pour des mots consécutifs.