Osiris6880
Messages postés36Date d'inscriptionvendredi 29 octobre 2004StatutMembreDernière intervention 7 décembre 2007
-
1 avril 2007 à 18:52
jmfmarques
Messages postés7666Date d'inscriptionsamedi 5 novembre 2005StatutMembreDernière intervention22 août 2014
-
15 avril 2007 à 20:07
Bonjour à vous tous,
Je programme en VB 2005 et je voudrais créer un algorithme permettant de faire toutes les permutations de colonnes possibles.
Je m'explique dans l'exemple suivant :
Dim chaine as string
Dim tableau_permut[] as string
Dim nombre_possibilite as double
chaine = "1234"
nombre_possibilite = 24 '(factorielle(len(chaine))) je ne me rappelle plus de la fonction factorielle
redim tableau_permut[nombre_possibilite]
Ensuite je voudrais executer une fonction qui fasse cela
tableau_permut[1] = "1234"
tableau_permut[2] = "1243"
tableau_permut[3] = "1342"
tableau_permut[4] = "1324"
tableau_permut[5] = "1423"
tableau_permut[6] = "1432"
tableau_permut[7] = "2431"
...etc.
Est ce que quelqu'un à quelque chose à me proposer ??
Osiris6880
Messages postés36Date d'inscriptionvendredi 29 octobre 2004StatutMembreDernière intervention 7 décembre 2007 4 avril 2007 à 22:38
Salut à vous tous,
Après avoir étudié le lien de jmfmarques, je me suis lancé dans mon algorithme.
Et j'ai réussis à le faire de façon a ce qu'il fonctionne quelque soit le nombre de chiffres.
Voici le code :
' Tableau qui contiendra les chaines possibles
Dim tableau() As String
Private Sub Form_Load()
' permutation et nombre de chiffres (ici 4)
permutation 4
End Sub
' Fonction facorielle
Public Function factorielle(Nombre As Double) As Double
Static i
factorielle = 1
For i = 1 To Nombre
factorielle = factorielle * i
Next
End Function
' Fonction recherchant si le nombre apparait dèjà dans la chaine
Public Function existe_pas(Nombre As Integer, Chaine As String) As Boolean
Static i
existe_pas = True
If Len(Chaine) = 0 Then Exit Function
For i = 1 To Len(Chaine) If (CDbl(Mid(Chaine, i, 1)) Nombre) Then existe_pas False
Next
End Function
' Fonction qui calcule les permutations
Public Function permutation(Nombre As Double)
' On redimmensionne le tableau
ReDim tableau(factorielle(Nombre))
Static n, i, x
Dim temp As Integer
n = 1
temp = 1
' tant que n est inférieur ou égale au nombre max
Do While (n <= Nombre)
'Fait une boucle de 1 à factorielle de nombre max divisé par factorielle du nombre max - n
For i = 1 To factorielle(Nombre) / factorielle(Nombre - n)
' Si temp dépasse le nombre max on le réinitialise à 1 If (temp (Nombre + 1)) Then temp 1
' Fait une boucle de 1 à factorielle de nombre - n
For x = 1 To factorielle(Nombre - n)
'Tant que le nombre existe dans la chaine
Do While existe_pas(temp, tableau(((i - 1) * factorielle(Nombre - n)) + x)) = False
' On incrémente temp et on vérifie qu'il ne dépasse pas le nombre max sinon on le rénitialise à 1
temp = temp + 1 If (temp Nombre + 1) Then temp 1
Loop
'On ajoute le caractère temp au tableau en cours
tableau(((i - 1) * factorielle(Nombre - n)) + x) = tableau(((i - 1) * factorielle(Nombre - n)) + x) & CStr(temp)
Next
' On incrémente temp
temp = temp + 1
Next
' On incrémente n
n = n + 1
Loop
End Function
chaibat05
Messages postés1883Date d'inscriptionsamedi 1 avril 2006StatutMembreDernière intervention20 novembre 20072 1 avril 2007 à 19:15
non Casy, ce qu' il veut c' est pouvoir répertorier
les permutations
Je me souviens l' avoir fait un jour.
Je vais voir si j' ai pas ça dans mon grenier...
Si je ne donne pas suite, c' est que je l' ai perdu...
Osiris6880
Messages postés36Date d'inscriptionvendredi 29 octobre 2004StatutMembreDernière intervention 7 décembre 2007 1 avril 2007 à 19:20
Merci Casi pour ton rappelle de la fonction factorielle mais ce n'est pas sa qui me pose problème.
En effet se sont les permutations, j'espére que chaibat05 vas retrouver sa fonction.
Merci quand même
Osiris6880
Vous n’avez pas trouvé la réponse que vous recherchez ?
chaibat05
Messages postés1883Date d'inscriptionsamedi 1 avril 2006StatutMembreDernière intervention20 novembre 20072 2 avril 2007 à 00:30
Bonsoir,
j' ai pas retrouvé le code mais j' ai essayé de le réécrire.
C' est pas tout à fait le même
Je ne l' ai pas eu le temps de le tester celui-ci, mais je crois
que ça doit être ça:
En prenant l' eemple de 4 colonne
Dim T() As String
n=0
Fot i=1 to 4
For j=1 To 4
For K=1 To 4
For l=1 To 4
n=n+1
Redim Preseve T(n)
If (i<>j) And (i<>k) And (i<>l) And (j<>k) And (j<>l) And (k<>l) Then _
T(n)=Str(i) & Str(j) & Str(k) & Str(l)
Next l
Next k
Next j
Next i
J' ai pas encore vu celeui proposé pr Marques, j' y vais à l' instant même
chaibat05
Messages postés1883Date d'inscriptionsamedi 1 avril 2006StatutMembreDernière intervention20 novembre 20072 2 avril 2007 à 04:17
recifiation: n' ajouter l' élément que si la condition est remplie...
For i = 1 To 4
For j = 1 To 4
For k = 1 To 4
For l = 1 To 4
If (i <> j) And (i <> k) And (i <> l) And (j <> k) And (j <> l) And (k <> l) Then
n = n + 1
ReDim Preserve T(n)
T(n) = Str(i) & Str(j) & Str(k) & Str(l)
End If
Next l
Next k
Next j
Next i
jmfmarques
Messages postés7666Date d'inscriptionsamedi 5 novembre 2005StatutMembreDernière intervention22 août 201427 2 avril 2007 à 09:16
Bonjour tous,
Ta solution, Chaibat, nécessite des boucles (ici i, j, k et l) imbriquées dont le nombre dépend de celui des chiffres à permuter et Osiris n'a pas dit qu'il n'avait que 4 chiffres, mais montré un exemple avec 4 chiffres... Comment faire de telles boucles en cvas de variations du nombre de chiffres à permuter ?
La solution figurant sur ce lien que j'ai trouvé libère de ce souci et utilise la récursivité, mais est assez pénible à suivre...
Je vais cette semaine essayrer (pour m'amuser un peu) d'appliquer une méthode analytique qui m'a été enseignée il y a 46 ans par un certain M. Frasnay et dont la finalité n'est pas uniquement celle de résoudre un problème de l'espèce du problème d'Osiris. Mais :
1) il va me falloir me rémémorer tout ce que nous avait, à l'époque, dit M. Frasnay sur la mise en oeuvre de ses méthodes.
2) il est à ce stade clair que je ne sais pas encore si cette méthode permettra de résoudre ce problème de permutations. Si oui (ce que j'espère) ce sera assez amusant. Si non : tant pis, mais j'aurai essayé...... et je n'aurai pas honte d'un éventuel échec.
jmfmarques
Messages postés7666Date d'inscriptionsamedi 5 novembre 2005StatutMembreDernière intervention22 août 201427 2 avril 2007 à 09:26
Quand même (pour le cas où d'autres souhaiteraient s'y mettre...)
Voilà le genre de matrice sur laquelle il conviendrait de se pencher (ici un exemple pour 1234) et qu'il est facile de faire dresser dynamiquement, quel que soit le nombre des éléments à permuter
chaibat05
Messages postés1883Date d'inscriptionsamedi 1 avril 2006StatutMembreDernière intervention20 novembre 20072 2 avril 2007 à 14:21
Bonjour Marques,
c' est vrai que c' est pas un model du genre
Et le problème c' est pas seulement que c' est
au cas par cas (autant de colonnes autant de boucles),
mais il y' a un autre problème qui est que le nombre
d' opérateur "And" dans une condition est limité
(je ne me souviens plus à combien)
On peut toujours le controuner en décomposant la condition
et en imbriquant, mais reste que c' est pas paramètrable...
On peut dire tout de même que ça reste jouable dans une
certaine mesure...
Toutours est-il que je me décourage pas à trouver mieux
Mais comme rien n' est parfait, côté temps d' éxécution, c' est pas génial !
Personnellement à moins de faire mieux que Jens G.Balchen,
(en moins de 12 lignes ), j' adopte son code...
mais je persisterai à être son chalenger quand même...!
Osiris6880
Messages postés36Date d'inscriptionvendredi 29 octobre 2004StatutMembreDernière intervention 7 décembre 2007 7 avril 2007 à 22:51
Tous d'abord merci pour tes remarques et tes compliments.
Cependant, comme tu l'a dit le temps d'éxecution n'est pas très bon.
Car pour avoir un temps de calcul optimun il faudrait faire qu'une boucle qui aille de 1 à factorielle(n) avec n étant le nombre max de chiffres.
Alors que dans mon code, on effectue une boucle allant de 1 à factorielle(n) * n.
Si tu a quelque chose de plus intéressant à me proposer, alors je prends !!!!
chaibat05
Messages postés1883Date d'inscriptionsamedi 1 avril 2006StatutMembreDernière intervention20 novembre 20072 8 avril 2007 à 00:18
salut,
je ne sais pas ce que je pourrais apporté de plus, car si tu as été conduit
à boucler autant de fois , c' est parce que ta logique t' y oblige.
Je pourrais seulement te dresser un bilan comparatif entre ton code et
celui de Jens G.Balchen.Tu pourras peut être en tirer des conséquences
lui (ou elle ) aussi boucle n* factoriel(n)
For i LBound(Elements) To UBound(Elements)> n
Permutate ArrayCount, RemoveFromArray(Elements, Element), Order, Orders ==> factoriel(n)
ce qui fait n * factoriel(n)
Mais ce qui te fais défaut dans ton code, c' est le fait d' être obligé à chaque passage
(n*factoriel(n) fois, de parcourir l' arrangement des élément déjà placés
(difficile de savoir combien de fois dans existe_pas puisqu' à chaque ajout tu refais
le test avec la partie précédente),
Tu vérifies alors si le prochain n' y est pas déjà.Alors que lui il n' a pas besoin de ça
puisqu' en l' éxcluant des élements à placer, il est certain qui y sera pas.
(j' espère que tu as saisi la tournure de ma phrase...un peu enchevetrée, mais logique
quand même ...)
Il faut donc voir de ce côté-ci...
Je ne penses pas qu' un Exit For dans existe_deja , si l' element existe,, apportera une
amélioration...je n' crois pas trop ..., ou très peu alors.
voilà donc mon point de vue.
PS: si j' ai fais référence à Jens G.Balchen , c ' est parce que je crois sincèrement que
c' est ce qu' il y' a de mieux
jmfmarques
Messages postés7666Date d'inscriptionsamedi 5 novembre 2005StatutMembreDernière intervention22 août 201427 8 avril 2007 à 00:18
Bonsoir,
J'avais commencé à réfléchir à l'utilisation de matrices, mais ai abandonné temporairement car je passe beaucoup de temps à essayer de trouver des bugs éventuels (résultant de cas particuliers non prévus) dans une application de saisies contrôlées de dates et heures sous divers formats d'affichage.
Celà me prend plus de temps que celui que j'ai passé à coder...
Je reviendrai ensuite sur mes matrices..
J'en étais arrivé à ce stade de réflexion :
Pour avoir toutes les combinaisons, la matrice doit avoir des lignes qui s'allongent également assez vite au fur et à mesure que le nombre d'éléments augmente et atteignent rapidemùent une très grande taille !
J'avais pensé à des décalages à calculer savamment pour éviter ces longueurs, ...
J'y reviendrai plus tard, c'est sur.
If ArrayLen = 1 Then
Order(Position) = Elements(LBound(Elements))
Orders.Add Order
Else
For i = LBound(Elements) To UBound(Elements)
Element = Elements(i)
Order(Position) = Element
Permutate ArrayCount, RemoveFromArray(Elements, Element), Order, Orders
Next i
End If
End Sub
Public Function RemoveFromArray(ByRef Elements() As Long, ByVal Element As Long) As Long()
Dim NewArray() As Long
Dim i As Long
Dim newi As Long
ReDim NewArray(LBound(Elements) To UBound(Elements) - 1)
For i = LBound(Elements) To UBound(Elements)
If Elements(i) <> Element Then
newi = newi + 1
NewArray(newi) = Elements(i)
End If
Next
RemoveFromArray = NewArray
End Function
---------------------------------------------------------
prcedure d' appel
Private Sub Command1_Click()
Dim Count As Long
Dim MonTableau() As Long, Temp() As Long
Dim Retour As Collection
ReDim MonTableau(3)
MonTableau(0) = 1
MonTableau(1) = 2
MonTableau(2) = 3
' j' ai aussi essayer en partant de MonTableau(1)=1
'rien à faire
'Redim Temp(3)
...
'MonTableau est le tableau à permuter (et je ne comprend pas
'pourquoi il doit être de type Long)
'Tem() est un tableau temporaire
'Retour() est celui qui doit retourner les permutations
Call Permutate(3, MonTableau(), Temp, Retour)
End Sub
jmfmarques
Messages postés7666Date d'inscriptionsamedi 5 novembre 2005StatutMembreDernière intervention22 août 201427 15 avril 2007 à 09:18
Bonjour et bon Dimanche,
Me revoilà...
J'abandonne l'idée d'utilisation de matrices car elle oblige également à passer par des factorielles.
Ma conclusion : trouver un système pour éviter ces factorielles...
J'ai une idée qui n'est pour l'instant qu'ébauchée dans ma cervelle et vais m'y mettre aujourd'hui.
Ce serait une solution complètement cinglée (j'aime ce genre de solution)... mais elle me parait devoir tenir la route
Cette solution, toutefois (au stade actuel de mes réflexions) ne dépasserait pas le traitement de 10 chiffres ou lettres.
J'aimerais toutefois que vous me donniez quelques indications sur la vitesse de vos résultats (en me précisant les performances de votre machine) pour 6 chiffres (par exemple)
jmfmarques
Messages postés7666Date d'inscriptionsamedi 5 novembre 2005StatutMembreDernière intervention22 août 201427 15 avril 2007 à 16:04
Re,
Bon (j'ai avancé...)
J'en suis à :
- résultat immédiat pour des permutations jusqu'à 5 chiffres inclus
- environ 1,7 secondes pour une permutation de 6 chiffres
Ma machine est tourne sous Windows 2000 et son horloge est de 2 GHertz
Je dois pouvoir encore améliorer (j'en suis à peu près certain) mais ne foncerais que si ces résultats sont bons comparés aux votres (pas l'intention de jouer à Don Quichote, si non)