Permutations de tableau
drillerdolls
Messages postés
8
Date d'inscription
lundi 1 décembre 2008
Statut
Membre
Dernière intervention
7 mai 2009
-
3 déc. 2008 à 19:23
drillerdolls Messages postés 8 Date d'inscription lundi 1 décembre 2008 Statut Membre Dernière intervention 7 mai 2009 - 5 déc. 2008 à 01:33
drillerdolls Messages postés 8 Date d'inscription lundi 1 décembre 2008 Statut Membre Dernière intervention 7 mai 2009 - 5 déc. 2008 à 01:33
5 réponses
cs_Orohena
Messages postés
577
Date d'inscription
vendredi 26 septembre 2008
Statut
Membre
Dernière intervention
20 novembre 2010
4
4 déc. 2008 à 01:00
4 déc. 2008 à 01:00
Bonjour
J'ai étudié un algorithme, j'aimerais savoir s'il te convient.
Ta fonction doit avoir un tableau de sauvegarde (copie de l'original), et un tableau de travail, ainsi que des pointeurs de permutation, tous déclarés en STATIC.
L'algorithme est le suivant :
1. Comparer le tableau reçu en paramètre avec le tableau de sauvegarde
Est-ce que les tableaux sont identiques ?
2. Oui : aller en 4
3. Non (le tableau reçu est un nouveau tableau) :
- recopier le tableau reçu dans le tableau de sauvegarde
- recopier le tableau reçu dans le tableau de travail
4. faire une permutation du tableau de travail
5. sortir et renvoyer le tableau de travail
Cet algorithme est conforme, je crois, fidèlement à ton analyse. Mais plutôt qu'une fonction, je pense qu'il serait mieux de créer une classe "tableau" avec deux membres principaux :
- une méthode "initialiser" chargeant le tableau dans une nouvelle instance de la classe
- une propriété "permutation", restituant la permutation suivante
Amicalement
J'ai étudié un algorithme, j'aimerais savoir s'il te convient.
Ta fonction doit avoir un tableau de sauvegarde (copie de l'original), et un tableau de travail, ainsi que des pointeurs de permutation, tous déclarés en STATIC.
L'algorithme est le suivant :
1. Comparer le tableau reçu en paramètre avec le tableau de sauvegarde
Est-ce que les tableaux sont identiques ?
2. Oui : aller en 4
3. Non (le tableau reçu est un nouveau tableau) :
- recopier le tableau reçu dans le tableau de sauvegarde
- recopier le tableau reçu dans le tableau de travail
4. faire une permutation du tableau de travail
5. sortir et renvoyer le tableau de travail
Cet algorithme est conforme, je crois, fidèlement à ton analyse. Mais plutôt qu'une fonction, je pense qu'il serait mieux de créer une classe "tableau" avec deux membres principaux :
- une méthode "initialiser" chargeant le tableau dans une nouvelle instance de la classe
- une propriété "permutation", restituant la permutation suivante
Amicalement
drillerdolls
Messages postés
8
Date d'inscription
lundi 1 décembre 2008
Statut
Membre
Dernière intervention
7 mai 2009
4 déc. 2008 à 13:09
4 déc. 2008 à 13:09
En fait je n'ai pas de tableau de sauvegarde. Le tableau d'entrée est le tableau précédemment modifié. Il faut juste que je trouve un algo qui me permette de permuter le tableau une fois et de le renvoyer en sortie, et de telle manière que si j'appelle mon algo avec une boucle for n!+1 fois, le tableau initial que j'avais rentré en paramètre soit renvoyé en sortie après ses n!+1 permutations. Quand je parlais plus haut de deux tableaux, cétait les tableaux d'entrée et de sortie.Je pensais traduire ce schéma en algo :
Prenons un tableau simple de 4 éléments 1|2|3|4 :
3 4==>chemin 1
2
4 3==>chemin 2
2 4==>chemin 3
1 3
4 2==>chemin4
2 3==>.........
4
3 2
2 etc...
3 etc...
4 etc... ==>chemin 4!
Je pense que si l'on suit ces 4!+1 permutations on retombe sur le chemin 1
Voila ce que je n'arrive pas à traduire en algo
Merci de votre aide!!
Prenons un tableau simple de 4 éléments 1|2|3|4 :
3 4==>chemin 1
2
4 3==>chemin 2
2 4==>chemin 3
1 3
4 2==>chemin4
2 3==>.........
4
3 2
2 etc...
3 etc...
4 etc... ==>chemin 4!
Je pense que si l'on suit ces 4!+1 permutations on retombe sur le chemin 1
Voila ce que je n'arrive pas à traduire en algo
Merci de votre aide!!
si j'ai bien compris cela revient à trouver toutes les combinaisons possibles entre n nombres (les n nombres doivent ètre tous différents)
soit 3 nombres ABC
ABC chemin1
ACB chemin2
BAC chemin3
BCA chemin4
CAB chemin5
CBA chemin6
Pour moi tu ne reviens pas au chemin 1 tu explores tous les chemins possibles
La théorie, c'est quand on sait tout et que rien ne fonctionne. La pratique, c'est quand tout fonctionne et que personne ne sait pourquoi.
GRENIER Alain
soit 3 nombres ABC
ABC chemin1
ACB chemin2
BAC chemin3
BCA chemin4
CAB chemin5
CBA chemin6
Pour moi tu ne reviens pas au chemin 1 tu explores tous les chemins possibles
La théorie, c'est quand on sait tout et que rien ne fonctionne. La pratique, c'est quand tout fonctionne et que personne ne sait pourquoi.
GRENIER Alain
cs_Orohena
Messages postés
577
Date d'inscription
vendredi 26 septembre 2008
Statut
Membre
Dernière intervention
20 novembre 2010
4
Modifié par Whismeril le 29/05/2014 à 15:24
Modifié par Whismeril le 29/05/2014 à 15:24
Bonjour
Ouh la la ! Bonjour la migraine sur ce problème ! Mais bon, après 3 heures de boulot et deux boîtes d'Alka Seltzer, je crois avoir trouvé une solution. J'essaie d'expliquer, parce que le code est plutôt abscond.
1 quand la procédure Principale appelle le Sub Permuter avec le paramètre init à True, le Sub Permuter initialise n pointeurs à 1, 2, 3... puis fait une copie du tableau.
Après cette initialisation, le Sub retourne son tableau, classé selon les pointeurs. Comme ces pointeurs sont juste initialisés le tableau renvoyé est identique au tableau reçu.
2 Aux appels suivants, et tant que le paramètre init est False, le Sub Permuter demande à la procédure Incrementer la combinaison de pointeurs suivante. Cette procédure incrémente les pointeurs en base n, et vérifie, par la fonction codeCorrect que chaque pointeur possède une valeur unique. Le Sub Permuter retourne son tableau classé selon les pointeurs, comme à l'étape 1.
Lorsque la procédure Incrémenter a épuisé toutes les combinaisons, elle s'auto-initialise ; on revient donc au point 1.
Ici, les éléments à permuter sont des lettres de l'alphabet, mais je suis sûr que tu n'auras aucun problème pour les remplacer par des entiers.
Il doit certainement y avoir des solutions mathématiques plus brillantes, hélas hors de portée de mes pauvres neurones :
Hé ! Dieu, si j'eusse étudié
Au temps de ma jeunesse folle
Et à bonnes meurs dédié,
J'eusse maison et couche molle !
Mais quoi ? Je fuyais l'école,
Comme fait le mauvais enfant.
En écrivant cette parole,
À peu que le coeur ne me fend.
Amicalement
Ouh la la ! Bonjour la migraine sur ce problème ! Mais bon, après 3 heures de boulot et deux boîtes d'Alka Seltzer, je crois avoir trouvé une solution. J'essaie d'expliquer, parce que le code est plutôt abscond.
1 quand la procédure Principale appelle le Sub Permuter avec le paramètre init à True, le Sub Permuter initialise n pointeurs à 1, 2, 3... puis fait une copie du tableau.
Après cette initialisation, le Sub retourne son tableau, classé selon les pointeurs. Comme ces pointeurs sont juste initialisés le tableau renvoyé est identique au tableau reçu.
2 Aux appels suivants, et tant que le paramètre init est False, le Sub Permuter demande à la procédure Incrementer la combinaison de pointeurs suivante. Cette procédure incrémente les pointeurs en base n, et vérifie, par la fonction codeCorrect que chaque pointeur possède une valeur unique. Le Sub Permuter retourne son tableau classé selon les pointeurs, comme à l'étape 1.
Lorsque la procédure Incrémenter a épuisé toutes les combinaisons, elle s'auto-initialise ; on revient donc au point 1.
Ici, les éléments à permuter sont des lettres de l'alphabet, mais je suis sûr que tu n'auras aucun problème pour les remplacer par des entiers.
<hr />
Option Explicit
Const NB = 4 ' nombre d'éléments à permuter
<hr />
'
Sub principale()
'
' Affiche les NB!+1 permutations des NB premiers
' caractères de l'alphabet dans la fenetre d'execution
'
Dim monTableau(1 To NB) As String
Dim i As Long
Dim j As Integer
Dim k As Long
Dim init As Boolean
Dim detailler As Boolean
Dim msg As String
For i = 1 To NB
monTableau(i) = Chr(Asc("A") + i - 1)
Next
detailler = True ' ne pas afficher le détail (conseillé pour n > 5)
'
' calcul de k = n! + 1
k = 1
For i = 1 To NB
k = k * i
Next
k = k + 1
Debug.Print "Permutations des caracteres " & Join(monTableau) & " (" & _
IIf(detailler, "avec", "sans") & " le détail)"
'
init = True ' force le Sub permuter a initialiser ses variables
For i = 1 To k ' boucle d'affichage de n!+1 permutations de monTableau
permuter monTableau, init If detailler Or i <bold>k Or i</bold> 1 Then afficher monTableau, i
Next
End Sub
<hr />
'
Sub permuter(ByRef tableau() As String, ByRef init As Boolean)
'
' Recherche de la permutation suivante des éléments du tableau
'
Static codes(1 To NB) As Integer
Static localTab(1 To NB) As String
Dim i As Integer
If init Then
For i = 1 To NB
localTab(i) = tableau(i)
Next
End If
Do
If init Then
init = False
For i = 1 To NB
codes(i) = i
Next
Else If incrementer(codes) <bold>0 Then init</bold> True
End If
Loop While init
For i = 1 To NB
tableau(i) = localTab(codes(i))
Next
End Sub
<hr />
'
Function incrementer(codes() As Integer) As Integer
'
' Recherche la combinaison de pointeurs pour la prochaine permutation
'
Dim i As Integer, cle As String
cle = calcCle(codes)
i = NB
Do
If codes(i) = NB Then
codes(i) = 1
i = i - 1
Else
codes(i) = codes(i) + 1
i = NB
End If
Loop Until (calcCle(codes) <> cle And codeCorrect(codes)) Or i = 0
incrementer = i
End Function
<hr />
'
Function codeCorrect(codes() As Integer) As Boolean
'
' Verifie que les pointeurs du tableau codes() sont uniques
'
Dim i As Integer
Dim j As Integer
i = 1
j = 1
Do
If j = NB Then
i = i + 1
If i < NB Then j = i + 1
Else
j = j + 1
End If
Loop Until codes(i) = codes(j) codeCorrect <bold>IIf(i</bold> j, True, False)
End Function
<hr />
'
Function calcCle(codes() As Integer) As String
'
' Calcule une cle unique pour une combinaison de pointeurs
'
Dim i As Integer
For i = 1 To NB
calcCle = calcCle & codes(i)
Next
End Function
<hr />
'
Sub afficher(monTableau() As String, rang As Long)
'
' affice la permutation courante dans la fenetre Execution (Ctrl+G)
'
Dim msg As String
Dim i As Integer
msg = ""
For i = 1 To NB
msg = msg & monTableau(i)
Next
Debug.Print Format(rang, String(NB, "0")) & " " & msg
End Sub<hr />
Il doit certainement y avoir des solutions mathématiques plus brillantes, hélas hors de portée de mes pauvres neurones :
Hé ! Dieu, si j'eusse étudié
Au temps de ma jeunesse folle
Et à bonnes meurs dédié,
J'eusse maison et couche molle !
Mais quoi ? Je fuyais l'école,
Comme fait le mauvais enfant.
En écrivant cette parole,
À peu que le coeur ne me fend.
Amicalement
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
drillerdolls
Messages postés
8
Date d'inscription
lundi 1 décembre 2008
Statut
Membre
Dernière intervention
7 mai 2009
5 déc. 2008 à 01:33
5 déc. 2008 à 01:33
Mille merci à toi!!!!!! Ton code marche niquel, j'ai plus qu'a l'adapter à mon problème. Tu en as meme fait plus que je demandais parce que seule ta fonction "incrémenter" me suffit...lol en effet mon tableau est un tableau d'entiers numérotés de 1 à 11 donc en fait tes clés de permutation sont mes tableaux permutés xD. Enfin je vais pas non plus te dire que ca va pas!!!(tout de meme...) Il aura quand meme fallu que je prenne un bon vieux stylo pour comprendre comment cette fonction marche et je comprends ta source de maux de tete.
Tres amicalement
Tres amicalement
