Doublons dans l'enumeration de toutes les permutations (combinaisons) 213 <-> 312

**electroremy** · 01/09/2014, 23h20

Bonjour,

Suite à mon précédent post (http://www.developpez.net/forums/d14...ux-dimenssion/)

J’ai implémenté, pour la recherche du chemin le plus court lorsque le nombre de perçage est faible (n<6) une méthode directe, plus performante que les algorithmes génétiques.

Cette méthode est simplement une énumération récursive de toutes les permutations possibles. Elle a été faite après avoir examiné un certain nombre de codes sur le net.

Voici le code :

(le code est dans la fonction recursive OptimiserOrdrePercages_Direct_CR)

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
 
Private Sub OptimiserOrdrePercages_Direct(out As OutilCNC)
    'Code directe pour out.ListePercage.count <6
    Dim per As PercageCNC
    Dim i As Integer
    Dim n As Integer
    Dim XP As Double, YP As Double
    Dim TmpListe As Collection
    Dim Debut As Single
    Dim msg As String
 
    Dim ListePos As Collection
    Dim Comb As Collection
    Dim MinComb As Collection
 
    Debut = Timer
    n = out.ListePercages.count
    If n > 2 And n < 6 Then
        'Calcul de la longueur avant optim :
        out.LongAvantOptim = 0
        Set per = out.ListePercages.Item(1)
        XP = per.Xmachine
        YP = per.Ymachine
        For i = 2 To n
            Set per = out.ListePercages.Item(i)
            out.LongAvantOptim = out.LongAvantOptim + Sqr((XP - per.Xmachine) * (XP - per.Xmachine) + (YP - per.Ymachine) * (YP - per.Ymachine))
            XP = per.Xmachine
            YP = per.Ymachine
        Next i
 
        'Choix :
        Call OptimiserOrdrePercages_Direct_CR(n, 0, out, ListePos, Comb, MinComb, -1)
 
        'Affectation :
        msg = ""
        Set TmpListe = New Collection
        For i = 1 To n
            msg = msg + Format(MinComb(i)) + " "
            Set per = out.ListePercages.Item(MinComb(i))
            TmpListe.Add per
        Next i
        Set out.ListePercages = TmpListe
 
        'Calcul de la longueur après optim :
        out.LongApresOptim = 0
        Set per = out.ListePercages.Item(1)
        XP = per.Xmachine
        YP = per.Ymachine
        For i = 2 To n
            Set per = out.ListePercages.Item(i)
            out.LongApresOptim = out.LongApresOptim + Sqr((XP - per.Xmachine) * (XP - per.Xmachine) + (YP - per.Ymachine) * (YP - per.Ymachine))
            XP = per.Xmachine
            YP = per.Ymachine
        Next i
 
        out.DebugInfo = "Calcul direct - Durée " + Format(Timer - Debut, "0.000") + "s - " + msg + out.DebugInfo
    Else
        If n = 2 Then
            Set per = out.ListePercages.Item(1)
            XP = per.Xmachine
            YP = per.Ymachine
            Set per = out.ListePercages.Item(2)
            out.LongAvantOptim = Sqr((XP - per.Xmachine) * (XP - per.Xmachine) + (YP - per.Ymachine) * (YP - per.Ymachine))
            out.LongApresOptim = out.LongAvantOptim
            out.DebugInfo = out.DebugInfo + "(pas d'optimisation, il n'y a que deux perçages)"
        Else
            out.DebugInfo = out.DebugInfo + "(pas d'optimisation, il n'y a qu'un perçage)"
        End If
    End If
 
End Sub
 
Private Sub OptimiserOrdrePercages_Direct_CR(ByRef NbPercages As Integer, ByVal Niveau As Integer, ByRef out As OutilCNC, ByRef ListePos As Collection, ByRef Comb As Collection, ByRef MinComb As Collection, ByRef MinLongComb As Double)
    Dim i As Integer
    Dim j As Integer
    Dim K As Integer
    Dim Lg As Double
    If Niveau = 0 Then
        Set ListePos = New Collection
        For i = 1 To NbPercages
            ListePos.Add i
        Next i
        Set Comb = New Collection
        Call OptimiserOrdrePercages_Direct_CR(NbPercages, Niveau + 1, out, ListePos, Comb, MinComb, MinLongComb)
    Else
        If Niveau = NbPercages Then K = 0
        For i = 1 To ListePos.count
            j = ListePos.Item(1)
            ListePos.Remove (1)
            Comb.Add j
            If Niveau = NbPercages Then
                'Comb contient la combinaison correspondant au parcours à tester :
                Lg = OptimiserOrdrePercages_Direct_Test(Comb, out)
                If MinLongComb < 0 Then 'Début :
                    MinLongComb = Lg
                    K = j
                Else
                    If Lg < MinLongComb Then
                        MinLongComb = Lg
                        K = j
                    End If
                End If
            Else
                Call OptimiserOrdrePercages_Direct_CR(NbPercages, Niveau + 1, out, ListePos, Comb, MinComb, MinLongComb)
            End If
            Comb.Remove (Comb.count)
            ListePos.Add (j)
        Next i
        If Niveau = NbPercages And K > 0 Then
            Set MinComb = New Collection
            For i = 1 To Comb.count
                MinComb.Add (Comb.Item(i))
            Next i
            MinComb.Add K
        End If
    End If
End Sub
Private Function OptimiserOrdrePercages_Direct_Test(Comb As Collection, out As OutilCNC) As Double
    Dim i As Integer
    Dim per As PercageCNC
    Dim XP As Double, YP As Double
    OptimiserOrdrePercages_Direct_Test = 0
    Set per = out.ListePercages.Item(Comb.Item(1))
    XP = per.Xmachine
    YP = per.Ymachine
    For i = 2 To out.ListePercages.count
        Set per = out.ListePercages.Item(Comb.Item(i))
        OptimiserOrdrePercages_Direct_Test = OptimiserOrdrePercages_Direct_Test + Sqr((XP - per.Xmachine) * (XP - per.Xmachine) + (YP - per.Ymachine) * (YP - per.Ymachine))
        XP = per.Xmachine
        YP = per.Ymachine
    Next i
 
    'DEBUGGAGE :
    out.DebugInfo = out.DebugInfo + vbCrLf
    out.DebugInfo = out.DebugInfo + "; Longueur : " + Format(OptimiserOrdrePercages_Direct_Test, "0.00")
    For i = 1 To Comb.count
        out.DebugInfo = out.DebugInfo + " " + Format(Comb.Item(i))
    Next i
    '
End Function

Ce code marche, mais il n’est pas optimal. Pourquoi ? Parce que la moitié des permutations sont équivalentes à l’autre moitié ; par exemple 3421 est équivalent à 1243 (longueur identique, disposition identique en inversant juste le sens de lecture de droite à gauche)

Il faut que je modifie cet algorithme (plus exactement le code de la fonction OptimiserOrdrePercages_Direct_CR) pour ne tester que la moitié des combinaisons. Comment y parvenir ?

Voici un exemple de l'affichage des résultats, donnant l’ordre dans lequel les combinaisons sont testées dans le cas n=4 :

1 2 3 4
1 2 4 3
1 3 4 2
1 3 2 4
1 4 2 3
1 4 3 2
2 3 4 1
2 3 1 4
2 4 1 3
2 4 3 1
2 1 3 4
2 1 4 3
3 4 1 2
3 4 2 1
3 1 2 4
3 1 4 2
3 2 4 1
3 2 1 4
4 1 2 3
4 1 3 2
4 2 3 1
4 2 1 3
4 3 1 2
4 3 2 1

Merci

A+

**DAUDET78** · 02/09/2014, 00h11

Je n'ai pas analysé ton code. Mais si tu génères 4213 , il est facile de stocker 4213 dans un tableau et 3124 dans un autre

Code :

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

1
2
3
4
5
6
7
8
9
10
11
    T1        T2
00 1 2 3 4   4 3 2 1
01 1 2 4 3   3 4 2 1
02 1 3 4 2   2 4 3 1 
03 1 3 2 4   4 2 3 1
04 1 4 2 3   3 2 4 1
05 1 4 3 2   2 3 4 1
06 2 3 4 1   1 4 3 2
07 2 3 1 4   4 1 3 2
08 2 4 1 3   3 1 4 2
etc etc

Tu recherches si T1(i) se trouve dans T2(x) . Si oui, tu supprimes T1(x)
Par exemple T1(05) est identique à T2(06) , on vire la case 06

**electroremy** · 02/09/2014, 19h58

Pas bête, ça ressemble à de la mémoïsation (stockage de données déjà calculées pour ne pas les recalculer)

avec ta solution :
- j'évite de calculer la fonction d'évaluation sur les permutations en double
- mais en contre partie je dois stocker les énumérations précédentes, et comparer chaque nouvelle énumération à toutes les énumérations précédentes générées

j'aurais préféré un algorithme dont le mécanisme de parcours n'énumère que les "bonnes permutations", c'est à dire ne générer que des permutations non orientées uniques

Mon algorithme d'énumeration récursif des permutations parcours en quelque sorte un arbre feuille par feuille, dont la moitié des feuilles sont superflues. (une feuille est 1234 ou 4321 ou 1423...) Il faudrait trouver une astuce permettant de ne pas calculer ces feuilles de façon efficace. Mon idée serait de trouver, pour chaque feuille, un critère simple et rapide à calculer me disant qu'elle est "gauche" :

Feuille "gauche" : 4321 - Feuille "droite" : 1234
Feuille "gauche" : 3142 - Feuille "droite" : 2413
Feuille "gauche" : 3124 - Feuille "droite" : 4213

Ma question : est-ce qu'une comparaison toute bête est correcte ? Rien ne m'interdit d'inverser droite et gauche pour certaines feuilles, ce qui donne en reprenant l'exemple précédant :

Feuille "gauche" : 4321 - Feuille "droite" : 1234
Feuille "gauche" : 3142 - Feuille "droite" : 2413
Feuille "gauche" : 4213 - Feuille "droite" : 3124

au passage, comment, en VB5, avoir des variables persistantes entre des appels récursifs de fonction (ce qui m'éviterais de tout passer en paramètre, ou d'utiliser des variables globales) ?

merci

**electroremy** · 02/09/2014, 20h01

J'ai une intiution :

Je vais essayer de voir si mathématiquement, le critère "1ier chiffre supérieur au dernier chiffre" est un bon critère d'exclusion des permutations en double

A+

**electroremy** · 02/09/2014, 22h11

Mon intuition est bonne, voici une démonstration :

Listons toutes les permutations possibles des n nombres de 1 à n.

Ensuite, trions les dans deux colonnes, de telle sorte qu’une ligne comporte deux permutations en miroir, ayant chacune une longueur de chemin identique*

Pour chaque ligne on a les deux permutations suivantes :

M1 M2 M3 … Mn | K1 K2 K3 … Kn

avec les conditions suivantes :

0 < Mi < n+1 quel que soit 0<i<n+1
0 < Ki < n+1 quel que soit 0<i<n+1
Si i<>j alors Mi <> Mj quel que soient 0<i<n+1 et 0<j<n+1
Si i<>j alors Ki <> Kj quel que soient 0<i<n+1 et 0<j<n+1
Quel que soit 0<i<n+1 on a Mi = Kn-i+1

* La longueur du chemin M est la somme des distances entre les points Mi et Mi+1 pour i allant de 1 à n-1
La longueur du chemin K est la somme des distances entre les points Kj et Kj+1 pour j allant de 1 à n-1
Il suffit de poser j = n-i+1 pour voir que la longueur du chemin M est bien identique à la longueur du chemin K.

La situation M1 = Mn ne se produit jamais, pour chaque ligne on a forcément M1 < Mn (cas 1) ou M1 > Mn (cas 2)

On a M1 = Kn et Mn = K1

Donc M1 < Mn implique K1 > Kn (cas 1)
Et M1 > Mn implique K1 < Kn (cas 2)

Si on élimine toutes les permutations correspondant au critère Q1 > Qn, (Q pouvant être M ou K) alors :
- pour chaque ligne dans le cas 1, on élimine la permutation K
- pour chaque ligne dans le cas 2, on élimine la permutation M

Après élimination des permutations correspondant au critère Q1 > Qn, on se retrouve bien avec une seule permutation par ligne. Les doublons ont été supprimés.

Comment produire un algorithme efficace, qui au lieu de construire toutes les combinaisons et de les tester pour en supprimer la moitié ne construira que les bonnes combinaisons ?
- il suffit de commencer par choisir M1 et Mn avec Mn < M1
- puis pour chaque couple M1 Mn possible, choisir les permutations possibles de M2 … Mn-1

**ProgElecT** · 02/09/2014, 23h06

Salut

En passant par une collection de type Dictionary (reference Microsoft Scripting Runtime (scrrun.dll)) plutôt qu'une collection de type VBA, tu bénéficiaires de la fonction Exists .
En remplissant la clé par la combinaisons, lors de la n+1 combinaison, avant de la mémoriser dans la collection tu pourrais faire une condition, si MavariableDictionary.Exists(StrReverse(n+1conmbinaison) est inégal à vraie, ajouter cette dernière combinaison dans mon tableau Dictionary.

Comme je ne suis pas sûr d'avoir réussis à me faire comprendre

un exemple de

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
Private Sub Command2_Click()
Dim DicO As Object
Set DicO = CreateObject("Scripting.Dictionary")
DicO.Add "1234", "1234"
DicO.Add "1324", "1324"
 
Dim NewDonner As Double
NewDonner = 4321 'non ajouté à la collection
'NewDonner = 4312'Ajouter à la collection
 
If DicO.Exists(StrReverse(CStr(NewDonner))) = False Then
    DicO.Add CStr(NewDonner), CStr(NewDonner)
    MsgBox "Ajouter à la collection"
    Else
    MsgBox "NewDonner non ajouté à la collection"
End If
 
Set DicO = Nothing
End Sub

en mettant en commentaire l'une l'autre des lignes 8 et 9, cela semble remplir les conditions que tu recherches.

**electroremy** · 03/09/2014, 01h02

Bon, ça marche ; de plus le code utilise deux niveaux de récursivité de moins grâce au choix préalable du premier et du dernier nombre

voici le code en VB5 :

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
Private Sub OptimiserOrdrePercages_Direct(out As OutilCNC)
    'Code directe pour out.ListePercage.count <6
    Dim per As PercageCNC
    Dim i As Integer
    Dim n As Integer
    Dim XP As Double, YP As Double
    Dim TmpListe As Collection
    Dim Debut As Single
    Dim msg As String
 
    'Dim ListePos As Collection
    'Dim Comb As Collection
    Dim MinComb As Collection
 
    Debut = Timer
    n = out.ListePercages.count
    If n > 2 And n < 6 Then 'REMARQUE : Il FAUT TESTER SI LE CALCUL DIRECT EST AUSSI JUDICIEUX POUR n=7, n=8 et n=9
        'Calcul de la longueur avant optim :
        out.LongAvantOptim = 0
        Set per = out.ListePercages.Item(1)
        XP = per.Xmachine
        YP = per.Ymachine
        For i = 2 To n
            Set per = out.ListePercages.Item(i)
            out.LongAvantOptim = out.LongAvantOptim + Sqr((XP - per.Xmachine) * (XP - per.Xmachine) + (YP - per.Ymachine) * (YP - per.Ymachine))
            XP = per.Xmachine
            YP = per.Ymachine
        Next i
 
        'Choix :
        'Call OptimiserOrdrePercages_Direct_CR2(n, 0, out, ListePos, Comb, MinComb, -1)
        Call OptimiserOrdrePercages_Direct_CR(MinComb, n, out)
 
        'Affectation :
        msg = ""
        Set TmpListe = New Collection
        For i = 1 To n
            msg = msg + Format(MinComb(i)) + " "
            Set per = out.ListePercages.Item(MinComb(i))
            TmpListe.Add per
        Next i
        Set out.ListePercages = TmpListe
 
        'Calcul de la longueur après optim :
        out.LongApresOptim = 0
        Set per = out.ListePercages.Item(1)
        XP = per.Xmachine
        YP = per.Ymachine
        For i = 2 To n
            Set per = out.ListePercages.Item(i)
            out.LongApresOptim = out.LongApresOptim + Sqr((XP - per.Xmachine) * (XP - per.Xmachine) + (YP - per.Ymachine) * (YP - per.Ymachine))
            XP = per.Xmachine
            YP = per.Ymachine
        Next i
 
        out.DebugInfo = "Calcul direct - Durée " + Format(Timer - Debut, "0.000") + "s - " + msg + out.DebugInfo
    Else
        If n = 2 Then
            Set per = out.ListePercages.Item(1)
            XP = per.Xmachine
            YP = per.Ymachine
            Set per = out.ListePercages.Item(2)
            out.LongAvantOptim = Sqr((XP - per.Xmachine) * (XP - per.Xmachine) + (YP - per.Ymachine) * (YP - per.Ymachine))
            out.LongApresOptim = out.LongAvantOptim
            out.DebugInfo = out.DebugInfo + "(pas d'optimisation, il n'y a que deux perçages)"
        Else
            out.DebugInfo = out.DebugInfo + "(pas d'optimisation, il n'y a qu'un perçage)"
        End If
    End If
 
End Sub
 
Private Sub OptimiserOrdrePercages_Direct_CR(ByRef MinComb As Collection, Optional NombrePercages As Integer, Optional outi As OutilCNC)
    'Compteurs pour les boucles for...next :
    Dim i As Integer
    Dim j As Integer
 
    'Variables pour la mesure de la longueure du chemin testé :
    Dim Lg As Double
    Dim per As PercageCNC
    Dim XP As Double, YP As Double
 
    Static Niveau As Integer      'Niveau de récursivité; Niveau = 0 => début, Niveau = NombrePercages => FIN
    Static ListePos As Collection 'Liste des chiffres restants pour le choix du chiffre du niveau en cours
    Static Comb As Collection     'Combinaison en cours de construction
    Static MinLongComb As Double  'Longueur de la plus petite combinaison déjà testée
    Static NbPercages As Integer  'Pour éviter de repasser sans arrêt NbPercage
    Static OutListePercages As Collection 'Liste des perçages, un perçage indique les coordonnées X,Y correspondant à un chiffre de la combinaison
    Static Dernier As Integer     'Dernier chiffre de la combinaison
 
    Static out As OutilCNC 'Pour affichage de debugage - à supprimer
 
    If Niveau = 0 Then 'Choix du premier chiffre et du dernier chiffre =================================================
        MinLongComb = -1
        NbPercages = NombrePercages
        Set OutListePercages = outi.ListePercages
        Set Comb = New Collection
 
        Set out = outi 'Pour affichage de debugage - à supprimer
 
        Niveau = 1
        'Choix du premier chiffre 'j' et du dernier chiffre 'Dernier' - On doit toujours avoir : j < dernier :
        For j = 1 To NbPercages - 1
            For Dernier = j + 1 To NbPercages
                Comb.Add j
                Set ListePos = New Collection
                For i = 1 To NbPercages
                    If i <> j And i <> Dernier Then ListePos.Add i
                Next i
                Call OptimiserOrdrePercages_Direct_CR(MinComb)
                Comb.Remove (Comb.count)
            Next Dernier
        Next j
        Niveau = 0
 
        Exit Sub
    End If
 
    'Pour chaque paire <premier,dernier> test des différentes combinaisons possibles des chiffres du milieu ============
 
    Niveau = Niveau + 1
    If Niveau < NbPercages Then
        For i = 1 To ListePos.count
            j = ListePos.Item(1)
            Comb.Add j
            ListePos.Remove (1)
            Call OptimiserOrdrePercages_Direct_CR(MinComb)
            Comb.Remove (Comb.count)
            ListePos.Add (j)
        Next i
    Else
        ' "Comb & Dernier" contient la combinaison correspondant au parcours à tester :
        'Mesure de la longueur :
        Lg = 0
        Set per = OutListePercages.Item(Dernier)
        XP = per.Xmachine
        YP = per.Ymachine
        For i = NbPercages - 1 To 1 Step -1
            Set per = OutListePercages.Item(Comb.Item(i))
            Lg = Lg + Sqr((XP - per.Xmachine) * (XP - per.Xmachine) + (YP - per.Ymachine) * (YP - per.Ymachine))
            XP = per.Xmachine
            YP = per.Ymachine
        Next i
 
        'Pour affichage de debugage - à supprimer -------------------------------
        out.DebugInfo = out.DebugInfo + vbCrLf
        out.DebugInfo = out.DebugInfo + "; Longueur : " + Format(Lg, "0.00")
        For i = 1 To NbPercages - 1
            out.DebugInfo = out.DebugInfo + " " + Format(Comb.Item(i))
        Next i
        out.DebugInfo = out.DebugInfo + " " + Format(Dernier)
        '------------------------------------------------------------------------
 
        'Sauvegarde du chemin dans MinComb si c'est le plus court :
        If MinLongComb < 0 Or Lg < MinLongComb Then
            MinLongComb = Lg
            Set MinComb = New Collection
            For i = 1 To NbPercages - 1
                MinComb.Add (Comb.Item(i))
            Next i
            MinComb.Add Dernier
        End If
    End If
    Niveau = Niveau - 1
End Sub

et voici un exemple de résultat :

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
55
56
57
58
59
60
61
; 5 perçages - Optimisation de la longeur : 197,26mm => 160,65mm - Calcul direct - Durée 0,001s - 1 3 4 5 2 
; Longueur : 160,65 1 3 4 5 2
; Longueur : 190,88 1 3 5 4 2
; Longueur : 219,97 1 4 5 3 2
; Longueur : 207,80 1 4 3 5 2
; Longueur : 229,01 1 5 3 4 2
; Longueur : 210,94 1 5 4 3 2
; Longueur : 208,51 1 2 4 5 3
; Longueur : 178,27 1 2 5 4 3
; Longueur : 227,79 1 4 5 2 3
; Longueur : 245,85 1 4 2 5 3
; Longueur : 236,82 1 5 2 4 3
; Longueur : 249,00 1 5 4 2 3
; Longueur : 216,21 1 2 3 5 4
; Longueur : 204,04 1 2 5 3 4
; Longueur : 224,47 1 3 5 2 4
; Longueur : 206,41 1 3 2 5 4
; Longueur : 244,53 1 5 2 3 4
; Longueur : 274,77 1 5 3 2 4
; Longueur : 197,26 1 2 3 4 5
; Longueur : 215,33 1 2 4 3 5
; Longueur : 205,53 1 3 4 2 5
; Longueur : 217,70 1 3 2 4 5
; Longueur : 264,85 1 4 2 3 5
; Longueur : 234,61 1 4 3 2 5
; Longueur : 220,09 2 1 4 5 3
; Longueur : 211,06 2 1 5 4 3
; Longueur : 231,49 2 4 5 1 3
; Longueur : 278,64 2 4 1 5 3
; Longueur : 248,41 2 5 1 4 3
; Longueur : 210,29 2 5 4 1 3
; Longueur : 198,71 2 1 3 5 4
; Longueur : 236,83 2 1 5 3 4
; Longueur : 286,35 2 3 5 1 4
; Longueur : 239,20 2 3 1 5 4
; Longueur : 227,03 2 5 1 3 4
; Longueur : 236,06 2 5 3 1 4
; Longueur : 179,76 2 1 3 4 5
; Longueur : 226,91 2 1 4 3 5
; Longueur : 267,40 2 3 4 1 5
; Longueur : 229,28 2 3 1 4 5
; Longueur : 247,35 2 4 1 3 5
; Longueur : 238,32 2 4 3 1 5
; Longueur : 206,53 3 1 2 5 4
; Longueur : 265,08 3 1 5 2 4
; Longueur : 294,17 3 2 5 1 4
; Longueur : 256,82 3 2 1 5 4
; Longueur : 274,88 3 5 1 2 4
; Longueur : 253,68 3 5 2 1 4
; Longueur : 217,82 3 1 2 4 5
; Longueur : 255,16 3 1 4 2 5
; Longueur : 305,46 3 2 4 1 5
; Longueur : 246,90 3 2 1 4 5
; Longueur : 234,73 3 4 1 2 5
; Longueur : 255,94 3 4 2 1 5
; Longueur : 272,67 4 1 2 3 5
; Longueur : 262,87 4 1 3 2 5
; Longueur : 284,08 4 2 3 1 5
; Longueur : 243,59 4 2 1 3 5
; Longueur : 213,35 4 3 1 2 5
; Longueur : 263,64 4 3 2 1 5

Pour ceux qui aiment l'optimisation, il y a moyen de réduire le calcul de la longueur en le faisant au fur et à mesure

De même, si on se passe de l'affichage de la longueur pour le débuggage, au lieu de comparer les distances, on peut comparer le carré de la distance en supprimant l'instruction SQR() dans le calcul de la longueur (SQR étant une instruction chronophage)

Doublons dans l'enumeration de toutes les permutations (combinaisons) 213 <-> 312

VB 6 et antérieur

Discussions similaires

Partager

Partager