[VB6] Exercice de Combinatoire

Version imprimable

19/01/2005, 11h01
fichtre!

[VB6] Exercice de Combinatoire

Bonjour,

Je cherche à coder une fonction qui me permettrais de récupérer toutes les combinaisons alphanumérique d'une chaine de 4 caractères (ex : AAAA, AAAB .... ABAA .... ZZZZ).

J'ai réussi avec des boucles imbriquées mais ce n'est pas très "élégant"

Quelqu'un a t'il déja été confronté à ce genre d'exercice ?

Merci d'avance,

ERic
19/01/2005, 12h16
HPJ

Pose ta question sur le forum Algo
Merci :wink:

Une seule boucle suffit :

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
Private Const LongueurMot As Long = 4
Private Const Alphabet As String = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
Private Dictionnaire() As String
 
Public Sub main()
    Dim Index As Long
    Dim Mot As String
    Dim A As Long
    Dim B As Long
    Dim C As Long
    Dim D As Long
 
    ReDim Dictionnaire(Len(Alphabet) ^ LongueurMot - 1)
 
    For Index = LBound(Dictionnaire) To UBound(Dictionnaire)
        D = Int(Index / Len(Alphabet) ^ 3)
        C = Int((Index - D * Len(Alphabet) ^ 3) / Len(Alphabet) ^ 2)
        B = Int((Index - D * Len(Alphabet) ^ 3 - C * Len(Alphabet) ^ 2) / Len(Alphabet))
        A = Index - D * Len(Alphabet) ^ 3 - C * Len(Alphabet) ^ 2 - B * Len(Alphabet)
 
        Mot = Chr(Asc("A") + D) & Chr(Asc("A") + C) & Chr(Asc("A") + B) & Chr(Asc("A") + A)
        Dictionnaire(Index) = Mot
    Next Index
 
    For Index = LBound(Dictionnaire) To UBound(Dictionnaire)
        Debug.Print Dictionnaire(Index)
    Next Index
End Sub

19/01/2005, 13h07
fichtre!

Merci CatBull, ton code marche impec et fait nettement plus "pro" que mes boucles for imbriquées.

HPJ --> l'algo n'est pas bien compliqué à écrire, par contre, le problème était de le transcire dans un langage que je ne maîtrise pas bien.
19/01/2005, 13h28
fichtre!

J'ai retiré la mention "résolu" car je me permet de poser la question subsidiaire :

CatBull, comment adapter ta fonction pour une chaine de longueur variable (ex. toutes les combi de 1à2 caractères ou de 3 à 4) ?

Merci d'avance.

Eric
19/01/2005, 13h34
Catbull

Actuellement, la décomposition est faite en dur et pour une longueur de 4. Il s'agit des variables A, B, C et D.

Il faut écrire une fonction spécifique qui décompose l'index du tableau en lettres. Ce n'est pas très compliqué.

Version paramétrable :

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
Private Const LongueurMot As Long = 6
Private Const Alphabet As String = "ABCDEF"
Private Dictionnaire() As String
 
Public Sub main()
    Dim Index As Long
 
    ReDim Dictionnaire(Len(Alphabet) ^ LongueurMot - 1)
    For Index = LBound(Dictionnaire) To UBound(Dictionnaire)
       Dictionnaire(Index) = GetMot(Index)
       Debug.Print Dictionnaire(Index)
    Next Index
End Sub
 
Private Function GetMot(Index As Long) As String
    Dim Decomposition() As Long
    Dim Reste As Long
    Dim I As Long
 
    ReDim Decomposition(LongueurMot - 1)
 
    For I = LBound(Decomposition) To UBound(Decomposition)
        Decomposition(I) = Int((Index - Reste) / Len(Alphabet) ^ (LongueurMot - 1 - I))
        Reste = Reste + Decomposition(I) * Len(Alphabet) ^ (LongueurMot - 1 - I)
    Next I
 
    For I = LBound(Decomposition) To UBound(Decomposition)
        GetMot = GetMot & Chr(Asc("A") + Decomposition(I))
    Next I
End Function

PS : La variable Reste est mal nommée. Il s'agit de l'exact contraire d'un reste mais je ne connais pas le nom approprié...

19/01/2005, 14h15
DarkVader
Si mes lointains souvenirs sont exacts,
le nombre de combinaisons au sein d'un groupe n fixe est égal à son factoriel soit n!
et le nombre de combinaisons de n éléments (ordre non compris) au sein d'un groupe de m éléments est m!/[(m-n)!n!]

Dans le cas évoqué on a donc m!n!/((m-n)!n!) qui simplifié donne m!/(m-n)!

m=26 : n=4
nComb = 26 x 25 x 24 x 23

soit
Code:

1 2 3 4 res=1 for x= m-n+1 to m res=res*x next
19/01/2005, 14h23
Catbull

Dans notre cas une lettre peut être réutilisée donc le calcul n'est pas :
26 * 25 * 24 *23
mais :
26 * 26 * 26 * 26

D'ou n^m
19/01/2005, 14h26
fichtre!

Un grand merci CatBull c'est tout à fait ça.

Cette fois c'est résolu pour de bon :D
19/01/2005, 14h27
DarkVader

Exact pas fait attention - c'est donc encore plus bête
m^n %)