Ordonnancement - test de toutes les séquences possibles

Signaler
Messages postés
4
Date d'inscription
lundi 20 avril 2009
Statut
Membre
Dernière intervention
20 février 2012
-
Messages postés
1566
Date d'inscription
mardi 26 décembre 2000
Statut
Membre
Dernière intervention
5 avril 2013
-
Bonjour à tous,

Cela fait quelques jours que je butte sur une macro qui me permettrait de faire un test de plusieurs solutions (macro utilisée plus tard dans un outil d'ordonnancement de production). Je m'explique :
- J'ai 4 produits : A, B, C, D,
- J'aimerais avoir tester les 4! solutions (soit 24 solutions) de séquencements : c'est à dire obtenir successivement dans les cellules A1, B1, C1 et D1 les 24 solutions ci-dessous. Mon problème est que je n'arrive pas à trouver l'algorithme de calcul pour echainer les séquences...

<colgroup><col style=\"WIDTH: 16pt; mso-width-source: userset; mso-width-alt: 768\" span=\"4\" width=\"21\" /></colgroup>----
A, B, C, D, ----
A, B, D, C, ----
A, C, B, D, ----
A, C, D, B, ----
A, D, B, C, ----
A, D, C, B, ----
B, A, C, D, ----
B, A, D, C, ----
B, C, A, D, ----
B, C, D, A, ----
B, D, A, C, ----
B, D, C, A, ----
C, A, B, D, ----
C, A, D, B, ----
C, B, A, D, ----
C, B, D, A, ----
C, D, A, B, ----
C, D, B, A, ----
D, A, C, B, ----
D, A, B, C, ----
D, B, A, C, ----
D, B, C, A, ----
D, C, A, B, ----
D, C, B, A

J'aimerais avoir votre avis/propositions pour ensuite appliquer le système à plus de produits (10 soit 3628800 solutions)

Merci d'avance pour votre aide,

Florian

3 réponses

Messages postés
38
Date d'inscription
dimanche 12 octobre 2008
Statut
Membre
Dernière intervention
30 juin 2010

Bonjour Florian,

Je me suis déjà posé cette question (par l'intermédiaire de réalisation d'un brute force dont la longueur de la chaine de sortie est variable).

Pour écrire toutes les possibilités de 2 produits (on remplace A par 1 et B par 2 pour des raisons de simplicité), il suffit s'imbriquer 2 boucles (console VB.NET) :
For i As UInteger = 1 To 4
   For j As UInteger = 1 To 4
      Console.Out.WriteLine(i & j)
   Next j
Next i
Console.In.ReadLine()


Le problème est que tu souhaites que le nombre de produit soit variable (notons le n). Je n'arrive pas à écrire cela sous forme itérative (il faudrait n boucles imbriquées). Peut-être qu'il est plus facile de l'écrire de façon récursive mais les réponses à ta question m'intéressent également !

Léo.
Messages postés
1
Date d'inscription
jeudi 26 novembre 2009
Statut
Membre
Dernière intervention
30 novembre 2009

Option Explicit
Option Base 1

Function decal(chaine As String, position As Long) As String
'cette fonction renvoie une chaine avec un decalalge sur les caracteres situés à droite de position
decal = Left(chaine, position - 1)
decal = decal & Right(chaine, 1) & Mid(chaine, position, Len(chaine) - Len(decal) - 1)
End Function


Function permute(ParamArray x() As Variant) As Variant
'cette fonction donne toutes les permutations possibles des valeurs recues en x
Dim boucle As Long
Dim lecture As Long
Dim ecriture As Long
Dim nbcol As Integer
Dim germe As String
Dim nbpermute As Long
Dim reponse As Byte
Dim depart As Long
Dim fin As Long
Dim index As Long
Dim modif As String
Dim matresu() As Variant
Dim paradresse() As Variant
Dim tempo As Variant
Dim litteral As Boolean
'on calcule le nombre de valeurs à permuter et de combinaisons résultantes
nbcol = UBound(x) + 1
nbpermute = 1
litteral = True
'détection sur le type de traitement
For boucle = 0 To nbcol - 1
If Len(x(boucle)) > 1 Then litteral = False
Next boucle
For boucle = 0 To nbcol - 1
nbpermute = nbpermute * (boucle + 1)
    'si on fait le calcul sur les valeurs littérales elles seront logées dans la chaine
    If litteral Then
    germe = germe & x(boucle)
    'sinon on va créer une adresse sous forme alpha
    Else
    germe = germe & Chr(boucle + 65)
    End If
Next boucle
reponse = MsgBox(prompt:="il y a " & nbpermute & " combinaisons possibles voulez vous continuer ?", Buttons:=4)
If reponse = 7 Then
permute = False
Exit Function
End If
' on va créer la matrice qui recevra les résultats
ReDim matresu(1 To nbpermute)
'l'amorce sera germe qui contient les valeurs initiales ou leurs adresses
matresu(1) = germe
' à ce stade le tableau n'a subi aucune transformation
index = 1
For boucle = 1 To nbcol - 1
' on recommencera l'opération autant de fois que de colonne -1
    fin = index
    For lecture = 1 To fin
    ' pour chaque élément contenu dans la matrice
    ' lecture de l'élement à modifier
        modif = matresu(lecture)
        For ecriture = 1 To nbcol - boucle
        index = index + 1
        modif = decal(modif, boucle)
              matresu(index) = modif
        Next ecriture
    Next lecture
Next boucle
If litteral Then
permute = matresu
Else
ReDim paradresse(1 To nbpermute, 1 To nbcol)
    For index = 1 To nbpermute
        For boucle = 1 To nbcol
        tempo = matresu(index)
        tempo = Mid(tempo, boucle, 1)
        tempo = Asc(tempo) - 65
        tempo = x(tempo)
        paradresse(index, boucle) = tempo
        Next boucle
    Next index
permute = paradresse
End If
End Function


Sub testpermute()
Dim resu As Variant
Dim ligne As Long
Dim colonne As Long
resu = permute("a", "b", "c", "d")
For ligne = 1 To UBound(resu)
MsgBox (resu(ligne))
Next ligne
resu = permute(12, "oui", 19.6)
For ligne = 1 To UBound(resu, 1)
  For colonne = 1 To UBound(resu, 2)
    MsgBox (resu(ligne, colonne))
    Next colonne
Next ligne
End Sub
Messages postés
1566
Date d'inscription
mardi 26 décembre 2000
Statut
Membre
Dernière intervention
5 avril 2013
6
Bonjour,

1) c'est quoi, ces "cellules" (dans VB.Net.... le thème choisi pour cette discussion !à ====>>> précise donc
2) c'est quoi :

Ordonnancement - test de toutes les séquences possibles

??

La liste de toutes les permutations possibles des éléments A,B,C,D ?

Dieu que les choses sont bplus claires lorsque :
1) précisées
2) exprimées de manière concise et ne laissant aucun doute (la terminologie existe... elle correspond à une pensée claire.... et le reste .... suit ... !)