Discussion :

[Gilles57-H-G]

Je cherche un algorithme, qui donne toute les combinaisons possibles avec (n) éléments, avec répétitions des caractères. L'algorithme doit trier les doubles évidement.


J'ai adapté cet algorithme en VB Express 2010, cela fonctionne, mais il n'y a pas la répétition des caractères

Code vb :

Sélectionner tout - Visualiser dans une fenêtre à part

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
65
66
67
68
69
70
71
72
73
74
75
 
Dim tablo_origine() As String
Dim tablo_test() As Boolean
Dim tablo_resultat() As String
 
//////////////////////////////////////////////////////////////////////////////////////////////
 
Private Sub Button1_Click
 
Dim i As Integer
Dim nElements As Integer
 
'dimensionnement du tableau d'origine et remplissage
ReDim tablo_origine(2)
 
 
'Alimente les éléments du tableau
tablo_origine(0) = "a"
tablo_origine(1) = "b"
tablo_origine(2) = "c"
 
nElements = UBound(tablo_origine)
 
ReDim tablo_test(nElements)
ReDim tablo_resultat(0)
'lancement de la procédure récursive
test(0)
End Sub
 
//////////////////////////////////////////////////////////////////////////////////////////////////////
 
Sub test(ByVal n As Integer)
 
Dim i As Integer, i1 As Integer
Dim s As String
 
 
For i = 0 To UBound(tablo_origine)
'si valeur non sélectionnée
If tablo_test(i) = False Then
tablo_resultat(n) = tablo_origine(i)
'si on a parcourru tout le tableau d'origine
If n = UBound(tablo_origine) Then
'on construit la chaine d'affichage
s = ""
For i1 = 0 To n
s = s & tablo_resultat(i1)
 
Next
 
 
'remplissage ListBox
ListBox1.Items.Add(s)
 
 
 
'sinon, on relance la procédure récursive
Else
'on coche la valeur déjà choisie
tablo_test(i) = True
'on prépare le tableau résultat
ReDim Preserve tablo_resultat(n + 1)
'on relance la procédure
test(UBound(tablo_resultat))
'on rétablit le tableau résultat d'avant
ReDim Preserve tablo_resultat(n)
'on décoche la valeur déjà choisie
tablo_test(i) = False
End If
End If
Next
 
End Sub
 
/////////////////////////////////////////////////////////////////////////

Ce qui donne comme résultat: abc, acb, bac, bca, cab, cba.

Alors que je voudrais aussi, aab, aac, bba ,bbc, cca, ccb.

Merci

[cs_ntd]

Salut,

En fait je trouve que c'est même plus simple avec la répétition des caractères

Tu prend ton tableau, "tablo_origine", et pour les chaque caractère, tu prend un élément dedans :

0,0,0 //tablo_origine(0),tablo_origine(0),tablo_origine(0) = aaa
0,0,1 //aab
0,0,2 //aac
0,1,0 //...
0,1,1
...
1,0,0
...
2,2,2

Ca se fait facilement en 3 boucles for imbriquées, mais tu peut toujours le faire par récursivité...

A moins que j'ai mal compris le problème ?

[Gilles57-H-G]

Je te remercie cs_ntd.

Je vais t'avouer un truc, je suis pas "capable" de comprendre cet algo.

Je l'ai récupéré et je l'ai adapté.

Je ne suis pas en mesure de le modifier.

[cs_ntd]

OK ! pas de souci

Bon je vais supposer que tu connais les mécanismes de programmation (boucles, tests, conditions...).

Après concernant le VB, je t'avoue que c'est moi qui n'y connais rien, donc je vais parler en pseudocode

Pour avoir toutes les combinaisons possibles avec (n) caractères, il suffit :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
DEBUT ALGO
 
//On suppose que tablo_origine est un tableau à (n) éléments
tablo_origine[0] = 'a'
tablo_origine[1] = 'b'
tablo_origine[2] = 'a'
...
tablo_origine[n-1] = '$' //un caractère quelquonque
//On a n éléments (on a commencé à 0).
 
FOR i=0 TO n-1 DO //FOR n°1
    FOR j=0 TO n1 DO //FOR n°2
        FOR k=0 TO n-1 DO //FOR n°3
            //On suppose que des additions de caractères donne une concaténéation
            //'a'+'b' = 'ab'
            ECRIRE(tablo_origine[i]+tablo_origine[j]+tablo_origine[k])
        NEXT
    NEXT
NEXT
 
FIN ALGO

A l'éxécution, ça va donner :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
On rentre dans le FOR n°1 : i=0
    On rentre dans le FOR n°2 : j=0
        On rentre dans le FOR n°3 : k=0
            On écrit 'aaa'
        k est inferieur à n, donc k devient k+1, soit 1
            On écrit 'aab'
        k est inferieur à n, donc k devient k+1, soit 2
            On écrit 'aac'
        ...
        k est égal à n-2, donc k devient k+1, soit n-1
            On écrit 'aa$'
        k est égal à n-1, donc on retourne à la boucle précédente

    j est inferieur à n, donc j devient j+1, soit 1
        On rentre dans le FOR n°3 : k=0
            On écrit 'aba'
        ...
        k est égal à n-2, donc k devient k+1, soit n-1
            On écrit 'ab$'
        k est égal à n-1, donc on retourne à la boucle précédente

    ...
    j est égal à n-2, donc j devient j+1, soit n-1
        On rentre dans le FOR n°3 : k=0
            On écrit 'a$a'
        ...
        k est égal à n-2, donc k devient k+1, soit n-1
            On écrit 'a$$'
        k est égal à n-1, donc on retourne à la boucle précédente

    j est égal à n-1, donc on retourne à la boucle précédente


i est inferieur à n, donc i devient i+1, soit 1
    On rentre dans le FOR n°2 : j=0
        On rentre dans le FOR n°3 : k=0
        ...
        k est égal à n-2, donc k devient k+1, soit n-1
            On écrit 'ba$'
        k est égal à n-1, donc on retourne à la boucle précédente

    ...
    j est égal à n-2, donc j devient j+1, soit n-1
        On rentre dans le FOR n°3 : k=0
        ...
        k est égal à n-2, donc k devient k+1, soit n-1
            On écrit 'b$$'
        k est égal à n-1, donc on retourne à la boucle précédente

    j est égal à n-1, donc on retourne à la boucle précédente
...

i est égal à n-1, donc on passe à l'instruction suivante

Et normalement, ça te donne toutes les combinaisons possibles.

A toi d'adapter mon code au VB ! Si tu a des soucis, il y a toujours le forum VB

A au fait, ton premiers code utilisais une technique de programmation, la récursivité. Si tu veux en savoir plus : http://recursivite.developpez.com/

Bon courage

[Gilles57-H-G]

Oui, j'ai les bases en programmation.

Je pense qu'il faut faire une fonction récursive

La finalité de ce prog, c'est de donner toutes les combinaisons possibles avec les 26 lettres de notre alphabet qui ont une valeur gématrique réduite donnée.

Valeur gématrique ordinale
A = 1, B = 2, C = 3, D = 4, E = 5,.... Z + 26.

Valeur gématrique réduite du mot : DE = 4 +5 = 9.

Ainsi, je pourrais avoir toute les combinaisons pour, Ex la valeur de 60,
comme, Ex : police, hôtel, ville.

Donc la première partie du programme (listage des combinaisons) doit être récursive.

Je sais que ce truc est ingérable avec 26 lettres, mais si je filtre avec ma condition de valeur, cela devrait pouvoir peut être fonctionner.

[cs_ntd]

Donc la première partie du programme (listage des combinaisons) doit être récursive

Pas nécessairement Toute fonction récursive peut être... euh linéarisée ? je ne sais plus le terme. Disons que toute fonction récursive peut être exprimable avec des boucles FOR, et que toutes les boucles FOR sont exprimables récursivement.

C'est une histoire de choix, desfois c'est plus simple de faire la chose récursivement qu'en imbriquant des boucles FOR, et vice versa. Mais il faut savoir que la récursivité est beacoup plus gourmande pour le système que des boucles FOR (bien qu'équivalentes sur le papier).


Bon ici, je pense que le plus simple est de faire un mélange des deux ^^

Je verrais bien une fonction qui prend comme argument, la chaîne courante.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
fonction(chaine):
    Si somme(chaine) est >= 60 : 
        ecrire(chaine) et on fait un return (on quitte la procédure).
    Sinon :
        Pour toute les lettres : 
            si  somme(concat(chaine,lettre[i])) >= 60 //Edit : j'avais mis <=, ce qui était faux
                écrire(concat(chaine,lettre[i])), return
            fin si 
            fonction(concat(chaine,lettre[i]))
        Fin pour
    Fin si
fin fonction

On peut faire mieux, mais l'autre solution à laquelle j'avais pensée (qui évite de se trimballer la chaine d'appel récursif en appel récursif) dépend un peu des possibilités du langage, et je ne sais pas ce qu'il est possible de faire en VB Express

Bon courage

[Gilles57-H-G]

J'ai enfin trouvé

Cet algo génère toute les combinaison de caractères avec les répétitions.

C'est du basic, MAIS, il ne FONCTIONNE PAS avec Microsoft Visual Basic 2010
Express.

VB 2010 ne reconnais pas les tableau commençant autrement qu'a l'indice 0.

Il faut coller ce code dans OpenOffice, et tout fonctionne parfaitement.

LOL J'ai perdu trois jour.

Code VBA :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
Sub Main
Dim chaine As String 
Dim PosLettre(1 To 4) As Integer 'initiale un tableau de n case pour un mot à n lettre 
chaine = "" 
PosLettre(1) = 1 
PosLettre(2) = 1 
PosLettre(3) = 1 
PosLettre(4) = 1 
'le premier chiffre correspond au nombre lettre de la chaine ex abc = 3 
' le deuxieme correspond au nombre de lettre voulue en sortie ex 3= aaa,aab,aac 2=aa,ab,ac 
GeneMot "abcd", PosLettre, chaine, 4, 4 
MsgBox chaine 
End Sub 
 
 
Public Function GeneMot(chaine As String, PosLettre As Variant, ch As String, LongeurChaine As Integer, nbLettreVoulue As Integer) 
While PosLettre(1) < LongeurChaine + 1 
For l = 1 To nbLettreVoulue 
a = a & Mid(chaine, PosLettre(l), 1) 
Next l 
ch = ch & a & Chr(13) 
For m = nbLettreVoulue To 1 Step -1 
If PosLettre(m) = LongeurChaine Then 
If m <> 1 Then 
PosLettre(m) = 1 
Else 
PosLettre(m) = PosLettre(m) + 1 
End If 
Else 
PosLettre(m) = PosLettre(m) + 1 
Exit For 
End If 
Next m 
GeneMot chaine, PosLettre, ch, LongeurChaine, nbLettreVoulue 
Wend 
end function