Discussion :

[gnusti]

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

[Pol63]

avec de la récursivité surement

[plume13]

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 !)

[MABROUKI]

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.....................

[plume13]

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;
        }

[gnusti]

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 ^^

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

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 ?!?

[plume13]

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...)

[gnusti]

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 !!

[Pol63]

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