IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

VB.NET Discussion :

Algo Listing des cas uniques possibles


Sujet :

VB.NET

  1. #1
    Membre régulier Avatar de gnusti
    Homme Profil pro
    Développeur .NET
    Inscrit en
    Février 2012
    Messages
    55
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Développeur .NET
    Secteur : Industrie

    Informations forums :
    Inscription : Février 2012
    Messages : 55
    Points : 77
    Points
    77
    Par défaut Algo Listing des cas uniques possibles
    Bonjour à tous,

    J'ai besoin de votre aide pour une question algorithmique.

    Voici le problème que je rencontre :

    Le contexte : Je suis en train de développer une application de planification pour laquelle les ressources nécessaires dépendent du fonctionnement ou non de certains secteurs. Par exemple, si le Secteur 1 (S1) fonctionne seul, j'ai une configuration. Si S1 et S2 fonctionnent, j'en ai une autre. Si c'est S1 et S3, encore une autre...

    Mon problème : je cherche à concevoir un algo qui me permettrait de lister l'ensemble des cas uniques possibles soit, pour 4 secteurs, le résultat suivant :
    • S1
    • S1 - S2
    • S1 - S3
    • S1 - S4
    • S1 - S2 - S3
    • S1 - S2 - S4
    • S1 - S3 - S4
    • S1 - S2 - S3 - S4
    • S2
    • S2 - S3
    • S2 - S4
    • S2 - S3 - S4
    • S3
    • S3 - S4
    • S4


    A noter :
    * Le nombre de secteurs peut varier de 1 à l'infini (en pratique ça ne devrait pas aller au delà de 10 mais il faut prévoir laaaarge).
    * S1 - S2 est identique à S2 - S1.
    * Les noms des secteurs seront définis par les administrateurs de l'application donc les traitements de chaînes ne sont pas possibles
    * Les identifiants peuvent présenter des "trous" étant donné le besoin d'historisation et la possibilité de stopper un secteur à une date donnée ou la possibilité de prévoir l'ouverture d'un secteur à une date future donnée.

    Pour une période donnée, je pourrais donc récupérer ce genre d'informations de ma BDD :
    ID | Libellé
    1 | Finance
    4 | Compta
    5 | Ressources humaines

    et pour ce cas là, le resultat serait alors :
    • 1
    • 1 - 4
    • 1 - 5
    • 1 - 4 - 5
    • 4
    • 4 - 5
    • 5


    Je pense vous avoir donné les informations nécessaires.

    Je n'ai pas besoin de code tout fait mais simplement de la manière de procéder.
    Au cas où il y aurais une fonction toute faite mais que je ne connaitrais pas, je développe en VB.NET

    Merciiiiiiiiiiiiiiiiiiiiii

  2. #2
    Expert éminent sénior Avatar de Pol63
    Homme Profil pro
    .NET / SQL SERVER
    Inscrit en
    Avril 2007
    Messages
    14 179
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Puy de Dôme (Auvergne)

    Informations professionnelles :
    Activité : .NET / SQL SERVER

    Informations forums :
    Inscription : Avril 2007
    Messages : 14 179
    Points : 25 133
    Points
    25 133
    Par défaut
    avec de la récursivité surement

  3. #3
    Membre confirmé

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Novembre 2011
    Messages
    244
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 46
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Novembre 2011
    Messages : 244
    Points : 574
    Points
    574
    Par défaut
    Hello,

    J'attire ton attention sur le fait que le nombre de combinaisons est égal à (2 exposant n) - 1 :
    - pour 2 éléments : 3 résultats,
    - pour 4 : 15 résultats,
    ...
    - pour 10 : 1023 résultats.

    Soit une progression exponentielle !
    L'algorithme que tu vas pouvoir mettre en place va quand même dépendre du nombre d'éléments max. Si ce nombre peut vraiment être grand, je partirais sur un algorithme qui donne pour une combinaison donnée, la combinaison suivante, histoire de ne pas avoir à stocker toutes les combinaisons.
    Par exemple, la combinaison en cours est (S1 S2), GetNextCombination() donne (S1 S3) dans ton exemple.
    Pour pouvoir calculer les combinaisons, j'utiliserais des tableaux :
    - un tableau à n entrées contenant les éléments triés :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    elt = Array(4)
    elt[0] = S1
    elt[1] = S2
    elt[2] = S3
    elt[3] = S4
    - un tableau à n entrées contenant les index des éléments de la combinaison en cours
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    int[] idx = Array(4)
    idx = [0,1,-1,-1] (pour (S1 S2)  par exemple)
    Pour avoir la combinaison suivante, on parcourt les éléments du tableau d'index, et on incrémente les colonnes les unes après les autres et toujours dans la même logique.

    C'est juste une piste (et mon code ne ressemble pas à du code !)

  4. #4
    Expert confirmé
    Inscrit en
    Avril 2008
    Messages
    2 573
    Détails du profil
    Informations personnelles :
    Âge : 64

    Informations forums :
    Inscription : Avril 2008
    Messages : 2 573
    Points : 4 446
    Points
    4 446
    Par défaut
    bonjour gnusti....
    De ce qui ressort de ta description des liaisons des secteurs c'est un graph et dans le cas d'espece simplement un arbre ou tree(graph sans cycle) ...
    Il peut etre represente par une matrice d'incidence noeud-noeud(tableau à 2 dimensions i,j)..
    Le terme "noeud" veut dire dans ta problematique "secteur"...
    Exemple :
    - List(of string) definissant les secteurs possibles (mettons N)...
    - Matrice d'Adjacence Noeud-Noeud AdjMatrix(N,N)....
    AdjMatrix vaut 1 (=> present dans la config) à l'intersection de la ligne et colonne (i,j)
    - si i=j => arc Si-Si ->Si lie à lui-meme (element diagonaux )..

    - si i<>j et i<j => arc Si -Sj (liaison Si,Sj) (elements dans partie triangulaire superieure (ce pour eviter la double liaison Sj -Si)...

    - sinon (i,j)=0 pour tous les autres elements (partie triangulaire inferieure) ...

    Quand un element (i,j) vaux -zero- dans AdjMatrix cela veut dire qu'il n'existe pas de liaison entre le secteur Si et Sj ou autrement il n'est pas present dans la configuration ...(ou arbre "calcule" à une date donne -t - par exemple)...
    Ceci fait que suivant ton exemple:

    Pour une période donnée, je pourrais donc récupérer ce genre d'informations de ma BDD :
    ID | Libellé
    1 | Finance
    4 | Compta
    5 | Ressources humaines
    AdjMatrix vaudra alors:
    Element diagonaux:
    -S1 correspond à AdjMatrix(1,1)=1
    -S4 '' AdjMatrix(4,4)=1
    -S5 " AdjMatrix(5,5)=1
    Element triangulaire superieur:
    -S1-S4 '' AdjMatrix(1,4)=1
    -S1-S5 '' AdjMatrix(1,5)=1
    -S4-S5 '' AdjMatrix(4,5)=1
    Element triangulaire inferieur(liaison double):
    -AdjMatrix(i,j)=0
    Pour tous les autres elements non presents dans la config:
    -AdjMatrix(i,j)=0

    voici un exemple de code pour mieux illustrer la chose:
    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
     
    'ajoute: 
    '-3 bouton
    '-un dgv 
    '-AdjMatrix est copie dans un datatable pour faciliter l'affichage 
    'des donnees
    Public Class Form1
        Private ListSecteurs As List(Of String)
        Private AdjMatrix(,) As Integer
        Private dtMatrix As DataTable
     
        Private Sub btnCreateSecteurs_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnCreateSecteurs.Click
            ListeSecteurs()
        End Sub
        Private Sub ListeSecteurs()
            'Init et Cree la liste des secteurs
            ListSecteurs = New List(Of String)( _
            New String() {"S1", "S2", "S3", "S4"})
     
            'cree un datable associe pour  l'affichage
            dtMatrix = New DataTable
            Dim myCol As DataColumn
            For Each s As String In ListSecteurs
                myCol = New DataColumn
                myCol.Caption = s
                myCol.ColumnName = s
                myCol.DataType = GetType(String)
     
                dtMatrix.Columns.Add(myCol)
            Next
        End Sub
        Private Sub btnCreateMatrix_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnCreateMatrix.Click
            AdjacenceMatrix()
        End Sub
        Private Sub AdjacenceMatrix()
            'Si liste vide retour
            If ListSecteurs.Count = 0 Then Return
            Dim N As Integer = ListSecteurs.Count
     
            'Init et Cree Matrice Adjacence "Secteur-Secteur"
            AdjMatrix = New Integer(N, N) {}
            For i = 0 To N - 1
                For j = 0 To N - 1
                    If i > j Then Continue For ' saute les elements diagonaux inferieurs
                    AdjMatrix(i, j) = 1
                Next
            Next
     
            'copie  AdjMatrix dans  la datable dtMatrix
            Dim dr As DataRow = dtMatrix.NewRow
            For i = 0 To N - 1
                For j = 0 To N - 1
                    dr.Item(j) = AdjMatrix(i, j)
                Next
                dtMatrix.Rows.Add(dr)
                dr = dtMatrix.NewRow
            Next
     
        End Sub
        Private Sub BtnDisplayMatrix_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles BtnDisplayMatrix.Click
            If dtMatrix Is Nothing Then Return
     
            'Prepare format des en-tetes de ligne
            Me.DataGridView1.RowHeadersVisible = True
            Me.DataGridView1.RowHeadersWidth = 20
     
            'binde le DGV à dtMatrix
            Me.DataGridView1.DataSource = dtMatrix
     
            'Affiche en-tete de ligne
            For Each row As DataGridViewRow In Me.DataGridView1.Rows
                If row.Index < ListSecteurs.Count Then
                    row.HeaderCell.Value = ListSecteurs(row.Index)
                End If
     
            Next
        End Sub
    End Class
    Si tu veux integrer le temps tu peux stocker la configuration calcule(arbre) dans chaque AdjMatrix dans un Dictionnaire Dictionary(of DateTime, AdjMatrix)....

    bon code.....................

  5. #5
    Membre confirmé

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Novembre 2011
    Messages
    244
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 46
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Novembre 2011
    Messages : 244
    Points : 574
    Points
    574
    Par défaut
    Sinon en y repensant cette nuit, j'ai trouvé une solution bien plus simple : comme le nombre de combinaisons est égal à (2^n - 1), autant utiliser cette propriété.
    Donc, en parcourant les nombres de 1 à (2^n - 1), et en comparant les valeurs des bits qu'ils contiennent à une représentation des éléments (secteurs) sous forme de bit aussi, on obtient tous les cas possibles.
    J'ai fait un exemple de code (en C#, désolé) :
    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
     
            /// <summary>
            /// Affiche toutes les combinaisons possibles
            /// </summary>
            public void DrawSolution()
            {
                // Récupération de toutes les valeurs possibles
                // string peut être remplacé par un objet Sector
                List<string> sectors = new List<string>();
                sectors.Add("S1");
                sectors.Add("S2");
                sectors.Add("S3");
                sectors.Add("S4");
                sectors.Add("S5");
                sectors.Add("S6");
     
                // on parcourt toutes les positions possibles
                StringBuilder result = new StringBuilder();
                for (long i = 1; i <= Math.Pow(2, sectors.Count); i++)
                {
                    IEnumerable<string> eligibleSectors = sectors.Where(sector => this.IsEligible(sectors.IndexOf(sector), i));
                    foreach (string t in eligibleSectors)
                    {
                        result.AppendFormat("{0} ", t);
                    }
     
                    result.AppendLine("<br/>");
                }
     
                Console.Write(result.ToString());
            }
     
            /// <summary>
            /// Evalue si un secteur est éligible au regard du nombre transmis (1 à la position correspondant au secteur dans la liste veut dire oui)
            /// </summary>
            /// <param name="sectorIndex">Un nombre 2^k</param>
            /// <param name="actualNumber">Un nombre de 1 à (2^n - 1)</param>
            /// <returns>True si le secteur est éligible</returns>
            private bool IsEligible(long sectorIndex, long actualNumber)
            {
                // on représente l'index du seteur en cours en puissance de 2, pour avoir une succession de 0 et un 1 au milieu
                long sectorNumber = (long)(Math.Pow(2, sectorIndex));
     
                // on utilise la propriété de comparaison de bits pour identifier l'éligibilité d'un secteur
                return (sectorNumber & actualNumber) == sectorNumber;
            }

  6. #6
    Membre régulier Avatar de gnusti
    Homme Profil pro
    Développeur .NET
    Inscrit en
    Février 2012
    Messages
    55
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Développeur .NET
    Secteur : Industrie

    Informations forums :
    Inscription : Février 2012
    Messages : 55
    Points : 77
    Points
    77
    Par défaut
    Citation Envoyé par plume13 Voir le message
    Hello,

    J'attire ton attention sur le fait que le nombre de combinaisons est égal à (2 exposant n) - 1 :
    - pour 2 éléments : 3 résultats,
    - pour 4 : 15 résultats,
    ...
    - pour 10 : 1023 résultats.

    Soit une progression exponentielle !
    Oui mais le métier le veux donc exponentiel ça sera ^^

    Citation Envoyé par plume13 Voir le message
    L'algorithme que tu vas pouvoir mettre en place va quand même dépendre du nombre d'éléments max. Si ce nombre peut vraiment être grand, je partirais sur un algorithme qui donne pour une combinaison donnée, la combinaison suivante, histoire de ne pas avoir à stocker toutes les combinaisons.
    Par exemple, la combinaison en cours est (S1 S2), GetNextCombination() donne (S1 S3) dans ton exemple.
    Pour pouvoir calculer les combinaisons, j'utiliserais des tableaux :
    - un tableau à n entrées contenant les éléments triés :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    elt = Array(4)
    elt[0] = S1
    elt[1] = S2
    elt[2] = S3
    elt[3] = S4
    - un tableau à n entrées contenant les index des éléments de la combinaison en cours
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    int[] idx = Array(4)
    idx = [0,1,-1,-1] (pour (S1 S2)  par exemple)
    Pour avoir la combinaison suivante, on parcourt les éléments du tableau d'index, et on incrémente les colonnes les unes après les autres et toujours dans la même logique.

    C'est juste une piste (et mon code ne ressemble pas à du code !)
    C'est, en gros, la façon dont je souhaitait le gérer mais l'ordre des secteurs n'ayant pas d'importance, idx = [true, true, false, false] fonctionnerait aussi bien.

    Mais j'en reviens au même "problème" : comment, via des boucles ou autre, faire switcher les true/false pour en sortir tous les cas en ayant en simultané :
    - 1 secteur à True et N-1 à False (N cas possibles)
    - 2 secteurs à True et N-2 à False (N! / 1!(N-1)! cas possibles)
    - ...
    - N-1 secteurs à True et 1 à False (N! / (N-1)!1! cas possibles
    - N secteurs à true (1 possibilité)

    Le tout en n'oubliant aucune des (2^N)-1 combinaisons

    Citation Envoyé par MABROUKI Voir le message
    bonjour gnusti....
    De ce qui ressort de ta description des liaisons des secteurs c'est un graph et dans le cas d'espece simplement un arbre ou tree(graph sans cycle) ...
    Il peut etre represente par une matrice d'incidence noeud-noeud(tableau à 2 dimensions i,j)..
    Le terme "noeud" veut dire dans ta problematique "secteur"...
    Exemple :
    - List(of string) definissant les secteurs possibles (mettons N)...
    - Matrice d'Adjacence Noeud-Noeud AdjMatrix(N,N)....
    AdjMatrix vaut 1 (=> present dans la config) à l'intersection de la ligne et colonne (i,j)
    - si i=j => arc Si-Si ->Si lie à lui-meme (element diagonaux )..

    - si i<>j et i<j => arc Si -Sj (liaison Si,Sj) (elements dans partie triangulaire superieure (ce pour eviter la double liaison Sj -Si)...

    - sinon (i,j)=0 pour tous les autres elements (partie triangulaire inferieure) ...
    ...

    bon code.....................
    Merci mais j'ai comme l'impression que tu oublies une "dimension":
    Si N = 1 : AdjMatrix(1)
    Si N = 2 : AdjMatrix(2, 2)
    Si N = 3 : AdjMatrix(3, 3, 3)
    Si N = 10 : AdjMatrix(10, 10, 10, 10, 10, 10, 10, 10, 10, 10)

    Ce qui devient assez difficile à gérer je pense ?!?

  7. #7
    Membre confirmé

    Femme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Novembre 2011
    Messages
    244
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 46
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Novembre 2011
    Messages : 244
    Points : 574
    Points
    574
    Par défaut
    Citation Envoyé par gnusti Voir le message


    C'est, en gros, la façon dont je souhaitait le gérer mais l'ordre des secteurs n'ayant pas d'importance, idx = [true, true, false, false] fonctionnerait aussi bien.

    Mais j'en reviens au même "problème" : comment, via des boucles ou autre, faire switcher les true/false pour en sortir tous les cas en ayant en simultané :
    - 1 secteur à True et N-1 à False (N cas possibles)
    - 2 secteurs à True et N-2 à False (N! / 1!(N-1)! cas possibles)
    - ...
    - N-1 secteurs à True et 1 à False (N! / (N-1)!1! cas possibles
    - N secteurs à true (1 possibilité)

    Le tout en n'oubliant aucune des (2^N)-1 combinaisons
    Je ne sais pas si tu as vu la solution que je propose (vu que nos réponses se sont un peu télescopées...)

  8. #8
    Membre régulier Avatar de gnusti
    Homme Profil pro
    Développeur .NET
    Inscrit en
    Février 2012
    Messages
    55
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Développeur .NET
    Secteur : Industrie

    Informations forums :
    Inscription : Février 2012
    Messages : 55
    Points : 77
    Points
    77
    Par défaut
    Citation Envoyé par plume13 Voir le message
    Je ne sais pas si tu as vu la solution que je propose (vu que nos réponses se sont un peu télescopées...)
    Nos réponses se sont effectivement télescopées et c'est effectivement LA solution.

    C'est tellement simple ! Comment ne pas y avoir pensé avant

    2^N - 1 mercis, tu m'enlève un tronc du pied Je vais pouvoir passer un bon week-end et arrêter de me prendre la tête avec ça

    Un petit merci de plus : merci !!

  9. #9
    Expert éminent sénior Avatar de Pol63
    Homme Profil pro
    .NET / SQL SERVER
    Inscrit en
    Avril 2007
    Messages
    14 179
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Puy de Dôme (Auvergne)

    Informations professionnelles :
    Activité : .NET / SQL SERVER

    Informations forums :
    Inscription : Avril 2007
    Messages : 14 179
    Points : 25 133
    Points
    25 133
    Par défaut
    Citation Envoyé par plume13 Voir le message
    Sinon en y repensant cette nuit, j'ai trouvé une solution bien plus simple : comme le nombre de combinaisons est égal à (2^n - 1), autant utiliser cette propriété.
    Donc, en parcourant les nombres de 1 à (2^n - 1), et en comparant les valeurs des bits qu'ils contiennent à une représentation des éléments (secteurs) sous forme de bit aussi, on obtient tous les cas possibles.
    J'ai fait un exemple de code (en C#, désolé) :
    bien réfléchi, et c'est surement le plus performant

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Récupérer la liste des type Mime possible
    Par sal.gass dans le forum Servlets/JSP
    Réponses: 0
    Dernier message: 28/02/2011, 15h08
  2. Paramétrer la liste des forums affichés, possible ?
    Par Yorick dans le forum Mode d'emploi & aide aux nouveaux
    Réponses: 2
    Dernier message: 27/04/2010, 10h34
  3. Listing des pannes informatiques possibles
    Par souminet dans le forum Ordinateurs
    Réponses: 1
    Dernier message: 22/03/2008, 04h05
  4. Liste des index unique
    Par magboom dans le forum Débuter
    Réponses: 3
    Dernier message: 15/02/2008, 17h43

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo