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

Voici un extrait de code vbs,
qui détermine toutes les combinaisons selon un choix de caractères mis à disposition dans un vecteur (abc..ABC..;:/!$..123..)
qui se nomme : vec_caractere()

Dans cette extrait de code, vous constaterez qu'il y a 6 boucle while, donc destiné à créer toutes les combinaisons de mots
d'une longeur de 6 caractères.

J'aimerais savoir comment faire pour optimiser l'écriture de ce code afin qu'il fonctionne pour les longeurs de mot de 1 à 12 caractères.

Car dans l'état actuel si je veux qu'il fonctionne de 1 à 12, je devrais copier/coller ce code l'un à la suite de l'autre
et soit enlever une ou plusieurs boucles while et/ou ajouter une ou plusieurs boucles while...

voici par exemple pour un mot de longeur 6 :

indice(1)=0
while (indice(1) <= limite_sup) and (resultat=false)
indice(2)=0
while (indice(2) <= limite_sup) and (resultat=false)
indice(3)=0
while (indice(3) <= limite_sup) and (resultat=false)
indice(4)=0
while (indice(4) <= limite_sup) and (resultat=false)
indice(5)=0
while (indice(5) <= limite_sup) and (resultat=false)
indice(6)=0
while (indice(6) <= limite_sup) and (resultat=false
combi =""
for l = 1 to longeur_actuel
combi = combi & vec_caractere(indice(l))
next
'msgbox combi

cpt(6) = cpt(6) + 1
totCpt = totCpt +1
resultat = isPassword(combi)

indice(6) = indice(6) + 1
wend '6
indice(5) = indice(5) + 1
wend '5
indice(4) = indice(4) + 1
wend '4
indice(3) = indice(3) + 1
wend '3
indice(2) = indice(2) + 1
wend '2
indice(1) = indice(1) + 1
wend '1

Une indication rapide : récursivité.

récursivité : je bloque, la récursivité ne résout pas le problème du nombre de boucle en rapport au nombre de la longeur.

Si tu as une solution (extrait de code) qui prouve le contraire, je suis prenneur...

Code:

---

1 2 3 4

ch est une chaîne ch = "abcdefghijkl" traite ( ch, "", 12)

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11

PROCEDURE traite(ch, ch_actuelle , n) i, t est un entier t = Taille( ch) SI n = 0 ALORS Trace( ch_actuelle) SINON POUR i = 1 A t traite ( ch, ch_actuelle + ch [[i]] , n-1) FIN FIN

---

C'est en langage 'Windev', mais tu devrais savoir adapter à n'importe quel langage.
Attention, pour des chaines de longueur 12, tu vas avoir des milliards de combinaisons, ce n'est absolument pas raisonnable de toutes les recenser.

Si je lance traite ( "abcd","",3) , j'obtiens bien les 64 réponses :

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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

aaa aab aac aad aba abb abc abd aca acb acc acd ada adb adc add baa bab bac bad bba bbb bbc bbd bca bcb bcc bcd bda bdb bdc bdd caa cab cac cad cba cbb cbc cbd cca ccb ccc ccd cda cdb cdc cdd daa dab dac dad dba dbb dbc dbd dca dcb dcc dcd dda ddb ddc ddd

---

De combinaisons, je trouve 479 millions

479 Millions ... pour un ""alphabet''' de combien de lettres, et des mots de quelle longueur ?

Dès que je rentre de vacance, je matte ton code tbc92,
en tout cas je te remercie d'avance pour ta réactivité et le temps que tu investis pour m'aider à y voir plus clair.

Car effectivement j'ai un peu de mal avec le côté abstrait de la récussivité, notamment par exemple
après un premier coup d'oeil sur ton code :
je n'arrive pas à comprendre comment cela ce fait que ch_actuelle change de valeur alors qu'il est qu'un paramètre parmi les deux autres ?

Il n'y a pas d'assignation sur ch_actuelle...

mais encore merci, je vais tester tout ca la semaine prochaine
et vous tiens au courant...

A+

Citation:

---

Envoyé par toni___

je n'arrive pas à comprendre comment cela ce fait que ch_actuelle change de valeur alors qu'il n'ai qu'un paramètre ?

---

:koi: ? Je vois trois paramètres à traite : ch, ch_actuelle et n. Sinon, pour comprendre ce code, fais-toi un exemple (simple !) sur papier : centralise-toi sur les appels de fonction (d'abord, on entre dans traite, puis on fait x autres appels à traite avec tels arguments, qui donnent à leur tour y appels à traite avec tels arguments, etc.), sous la forme d'un arbre (un appel, puis des flèches vers les appels qui en découlent, puis encore des flèches vers les noueaux appels, etc.).

ch_actuelle change de valeur alors qu'il est qu'un paramètre parmi les deux autres ?

Il n'y a pas d'assignation sur ch_actuelle...

A proprement parler, ch_actuelle ne change pas de valeur.
Au premier appel de traite, ch_actuelle est une chaîne vide, et n vaut 12
Puis traite ouvre une nouvelle session de traite (une nouvelle fenêtre en quelque sorte) et dans cette nouvelle session, ch_actuelle vaut "a", et n vaut 11.
Et dans cette session, idem, on ouvre une autre session de traite, avec "aa" et 10
etc etc
Si tu exécutes ce traitement avec un outil de type debugger, tu verras qu'à un instant t, tu peux avoir jusqu'à 12 variables ch_actuelle en même temps,avec 12 contenus différents.

Si je parlais de voir tous les appels effectués avec les paramètres, il y a une raison ;). Tu n'as jamais deux appels à traite avec la même valeur de ch_actuelle. Fais cet exercice (avec un débogueur comme le suggère tbc92 ou sur papier), tu comprendras nettement mieux ce qui se passe !

Bonjour
Si j'ai bien suivi la discussion, il s'agit de créer toutes les combinaisons possibles de M lettres dans une chaine de N lettres.
Cela peut se faire sans récursivite :

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 30 31 32 33 34 35 36 37 38 39 40 41 42 43

ch est un tableau caractères de taille M nch est le tableau de lettres à afficher de taille N ind est un tableau de taille N   initialisation de nch pour i de 1 a N faire nch[i] <- ch[1]   initialisation de ind pour i de 1 a N faire ind[i] <- 1   // la boucle infernale i <- N tant que i > 0 faire afficher nch   // incrementation du compteur de la lettre courante ind[i] <- ind[i]+1   // tant qu'on depasse le maximum des possibilites // on descend dans le tableau des indices tant que i > 0 && ind[i] > M faire // on reajuste le compteur de la lettre ind[i] <- 1   // on met la bonne lettre dans la chaine nch[i] <- ch[ind[i]]   // on decremente l'indice de la lettre i <- i - 1 // on incremente le compteur si on n'est pas // en debut de chaine si i > 0 alors ind[i] <- ind[i]+1 fin si fin tant que   si i > 0 alors nch[i] <- ch[ind[i]] i <- N fin si fin tant que

---

J'avoue que, dans ce cas, ce n'est pas testé, mais j'ai déjà plusieurs fois utilisé un code similaire pour le même genre de problème.

OK les gars, j'ai retranscrit le code récurssif windev en vbscript ci-dessous :

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 30 31 32 33 34 35

'VBScript : To run this script, save this code into UTF-8(sans Bom) file or Unicode !   dim fs,fname set fs=CreateObject("Scripting.FileSystemObject") set fname=fs.CreateTextFile("debug.txt",true)   dim cpt_combi cpt_combi = 0   dim ch ch = "abc"   traite ch, "", 3   fname.Close set fname=nothing set fs=nothing   sub traite (byval ch, byval ch_actuelle , byval n)   dim i, t   t = len(ch)   if (n = 0) then cpt_combi = cpt_combi +1 fname.WriteLine(cpt_combi & " " &ch_actuelle) else for i=1 to t traite ch,ch_actuelle & mid(ch,i,1),n-1 next end if   end sub

---

Ca tourne Nikel !

Maintenant je n'ai plus qu'à mettre traite dans une boucle et changer la valeur du 3 ème paramètre
afin de créer les combinaisons de toute les longeurs que je veux exemple de 1 à 12.

Maintenant on peu dire que la façon optimale niveau écriture du code, est bien la façon récurssive !

Mais une question très importante ce pose, étant donné que la pile d'une récursivité est limité à 1000,
ne va-ton pas bloquer un moment donné ?
et faire éffondrer le mythe comme quoi la récursivité est la façon la plus propre, optimisée et la plus professionnelle pour coder ?..

Citation:

---

Envoyé par toni___

et faire éffondrer le mythe comme quoi la récursivité est la façon la plus propre, optimisée et la plus professionnelle pour coder ?..[/COLOR]

---

Où as-tu lu ça ? La plus propre, ça se défend parfaitement selon les cas. Pour le reste, pour vraiment optimiser un code récursif, il faut qu'il soit terminal, donc user de trucs de sioux pour y arriver (alors qu'une simple boucle n'en a pas besoin). Professionnel ? Pas grand monde l'utilise…

Citation:

---

Envoyé par toni___

Mais une question très importante ce pose, étant donné que la pile d'une récursivité est limité à 1000,
ne va-ton pas bloquer un moment donné ?

---

D'où l'intérêt d'un code itératif sans empilement... ;)

Pour notre exemple de code de combinaison (qui pourrait faire penser à une force brute, si besoin ;-) lol)
Quelle est donc la façon la plus professionnelle de coder :

- soit copier/coller x fois tout le toin toin de bloc avec plein d'itération ?

- soit "include code dynamique" ?
rem :
entre copier/coller bloque qui n'est pas pro dutout! et la façon récursive (dont la pile récursive est limité à 1000),
j'ai créé une solution intermédiaire, qui est de créer dynamiquement le bloc de code dans un fichier externe et de l'inclure
au moment voulu dans le programme principal.
cette façon intermédiaire, je la nomme "include code dynamique".

- soit récursivité ?

- soit vous qui êtes PRO et qui lisez ce forum, dites moi comment vous auriez coder cela de manière la plus professionnel ...

cela m'intrigue et m'interresse.

Quand tu parles de limite à 1000 pour la récursivité, c'est le nombre de sessions simultanées de cette fonction traite(). Ici, sur l'exemple donné, tu ne dépasseras pas 12, donc on est très loin de la limite de 1000.

Tu auras un problème si tu utilises cette méthode pour concaténer successivement 1000 caractères. Mais de toutes façons, si tu dois générer toutes les chaines de 1000 caractères, il va y en avoir beaucoup beaucoup !

salut,

juste pour apporter ma pierre au dentifrice, de mon point de vue cet exercice là spécifiquement est presque le cas d'école de la bonne utilisation de la récursivité; le code est bien plus clair, à moins de générer un "mot de passe" de plusieurs milliers de caractères on est assuré de ne pas exploser la stack et assez souvent la version récursive sera y compris plus performante ou au moins aussi rapide (certains interpréteurs/compilateurs déroulant de manière systématique une récursion terminale en une itération, comme je crois Lisp notamment)
je me permets de link une discussion sur le même sujet, l'intérêt étant l'implém. en C d'une part et le mini-bench sans appel d'autre part

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

Bonjour,

Déjà, on peut se poser la question de pourquoi lister la totalité des combinaisons ?
Est-ce juste pour les afficher ?
Ou est-ce pour les stocker dans un tableau pour ensuite les utiliser ?
Si c'est le deuxième cas, ne vaudrait-il pas mieux de créer une fonction qui calcul la n-ieme chaine de la combi en question ?
Pas besoin de parcourir l'ensemble jusqu'à la n-ieme, c'est calculable...