Discussion :

[ffomnislash]

Bonjour,

J'ai un petit problème d'algorithme et je cherche la méthode la plus simple pour le résoudre (pas nécessairement la plus efficace dans le temps d’exécution)

Je dispose de n listes

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
l1 = a, bb, c, pp
l2 = a, r, l, pp
l3 = r, c , pp

le résultat que j'aimerais obtenir (il peut y avoir plusieurs solutions):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
res = a, bb, r, c, l, pp

Les contraintes sur le résultats:
- unicité des éléments (facile)
- si 'a' se trouve avant 'b' dans une des listes il doit alors se trouver avant 'b' dans le résultat

je suis sur que je peux y arriver en cherchant un algo mais ça risque de ne pas être lisible.
Connaissez vous un algo qui résout ce problème ?

[Franck Dernoncourt]

En utilisant une liste chainée, cela devrait être plutôt immédiat :

• Construction de la liste chainée à partir de la première liste ;
• Parcours des autres listes : si un élément non présent dans ta liste chainée, alors l'ajouter au bon endroit.

Si besoin de performance, tu pourrais par exemple maintenir un set en parallèle contenant les éléments de la liste chaînée (mais non ordonnés bien sûr).

Effectivement, comme tu le remarques, plusieurs solutions sont possibles et en outre il peut y avoir des incohérences entre les listes en input (eg L1 : a -> r; L2 : r -> a)

[Alikendarfen]

En utilisant une liste chainée, cela devrait être plutôt immédiat :

• Construction de la liste chainée à partir de la première liste ;
• Parcours des autres listes : si un élément non présent dans ta liste chainée, alors l'ajouter au bon endroit.

Ca me semble un peu plus compliqué que ça : en effet, lorsqu'on traite une liste parmi les autres listes, on fait un choix qui peut s'avérer contradictoire avec l'ordre imposé par une liste suivante...

On pourrait peut être constituer un graphe orienté :
- Partir de la première liste : le graphe G est alors les éléments de la liste, dans l'ordre
- Puis pour une liste suivante constituer un graphe g, identiquement, puis fusionner g dans G (à cette étape on doit pouvoir identifier les incompatibilités). Cette fusion crée des "ponts" entre les mines communes à g et G.

A l'issue G doit permettre de parcourir toutes les solutions... mais même ayant G, ça n'est pas super simple... ! car les "ponts" peuvent se chevaucher les uns les autres

Problème intéressant, cependant...

[Alikendarfen]

En fait, peut être qu'un simple tri pourrait être une bonne base ?

Si on reprend l'exemple de ffomnislash :

l1 = a, b, c, p
l2 = a, r, l, p
l3 = r, c , p

On a :
l1 => a < b, a < c, a < p et b < c, b < p et c < p
l2 => a < r, a < l etc...

On crée un table (deux dimensions avec chaque élément en ligne et en colonne) avec toutes les comparaisons connues (dans la construction de cette table on identifie au passage les contradictions).

Puis on trie les éléments selon les comparaisons de la table. Dans le cas où deux éléments n'ont pas de contrainte entre eux, on les considère comme égaux...

Le problème restant est que ça peut laisser des "trous" (du type x = y et x = z mais y < z) qui ferait planter / boucler un algo de tri...
... auquel cas, si on cherche une solution (parmi toutes), il suffit peut être de lever arbitrairement une contrainte (laisser x = y et imposer x < z) ?

[Franck Dernoncourt]

Ca me semble un peu plus compliqué que ça : en effet, lorsqu'on traite une liste parmi les autres listes, on fait un choix qui peut s'avérer contradictoire avec l'ordre imposé par une liste suivante...

Ah oui, il y a ce problème aussi (une solution serait pour chaque élément de chaque sous-liste de vérifier s'il est à la bonne place dans la liste chaînée)... Il faudrait que ffomnislash nous dise si tous les cas peuvent se produire ou pas, et quelles sont ses politiques vis-à-vis des incohérences (les détecter ? les ignorer ? etc).

[Nebulix]

Une simple concaténation
l1 = a, bb, c, pp
l2 = a, r, l, pp
l3 = r, c , pp
->
a, bb, c, pp, a, r, l, pp, r, c , pp
suivie de l'élimination des doublons
ne suffit elle pas ?
(je suppose que le problème est possible, c'est à dire que on n'a pas
l1=a,b,..
l2= b,a,...)

[Alikendarfen]

Voici une approche pas trop compliquée qui semble fonctionner :


Le principe général est le suivant :
- Soit un ensemble L de listes Li définissant des relations d'ordre entre les éléments eij de ces listes : eij < eij+1

- Soit une table T à deux entrées telle que :
T[e1,e2] = 0 si e1 et e2 n'ont pas de contraintes
T[e1,e2] = -1 si e1 < e2
T[e1,e2] = 1 si e1 > e2
Quand on affecte T[e1, e2] = V, alors on affecte également automatiquement T[e2, e1] = -V.

On initialise la table T avec toutes les contraintes exprimées par L :
Li = ei1, ei2, ... ein
V eij de Li, V k > j, alors
- T[eij, eik] = -1
- et V eix tel que T[eik, eix] = -1, alors T[eij, eix] = -1

A l'issue la table contient donc toutes les contraintes exprimées directement ou indirectement par L.

Ensuite il reste des zéros. Ces zéros correspondent à des couples d'éléments sans contraintes.

S'il y a un seul zéro dans la colonne (ou la ligne) pour un élément, pas de problème, on considère que les deux éléments sont équivalents.

S'il y a deux zéros, il y a possiblement contradiction. Cas du type e1 = e2, e1 = e3, mais e2 < e3. On lève donc la contradiction en affectant arbitrairement une contrainte entre e1 et e2.

Ceci étant fait, il suffit d'appliquer un algo de tri en utilisant le tableau pour définir la relation d'ordre.

En code, ça donne ça :
(note : les fonctions retournent false s'il y a une affectation contradictoire)

Partie principale :

Code C# :

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
 
        static void Main( string[] args )
        {
            // Lecture des données du problème depuis fichier
            List<List<string>> listes = ObtenirListes( _nomFichier );
 
            // Récupération des noms uniques des éléments sur l'ensemble des listes
            List<string> elements = ObtenirElements( listes );
 
            // Création de la table
            Table table = new Table( elements );
 
            // Indique une contradiction lors de calculs
            bool contradictoire = false;
 
            // Initialise chaque liste dans la table
            foreach ( List<string> liste in listes )
            {
                if ( Initialiser( table, liste, elements ) == false )
                {
                    contradictoire = true;
                    break;
                }
            }
 
            Afficher( table, elements );
 
            // Si pas de contradiction, on force les choix pour les éléments n'ayant pas de contrainte entre eux
            if ( contradictoire == false && ForcerLesChoix( table, elements ) == false )
                contradictoire = true;
 
            Afficher( table, elements );
 
            // Si pas de contradiction, on trie les éléments selon l'ordre indiqué par le tableau
            if ( contradictoire == false )
                elements.Sort( ( a, b ) => table.Get( a, b ) );
        }

Initialisation des listes :

Code C# :

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
 
        static bool Initialiser( Table table, List<string> liste, List<string> elements )
        {
            // Pour les n-1 premiers éléments de la liste
            for ( int i = 0 ; i < liste.Count - 1 ; i++ )
            {
                string element1 = liste[i];
 
                // Pour chaque élément suivant cet élément
                for ( int j = i + 1 ; j < liste.Count ; j++ )
                {
                    string element2 = liste[j];
 
                    // Affectation de la relation d'ordre à ce couple d'éléments
                    if ( Initialiser( table, element1, element2, -1, elements ) == false )
                        return false;
                }
            }
 
            return true;
        }
 
        static bool Initialiser( Table table, string element1, string element2, int valeur, List<string> elements )
        {
            // Affecte la valeur dans le tableau
            if ( table.Set( element1, element2, valeur ) == false )
                return false;
 
            // Induit les relations d'ordre indirectes
            foreach ( string element in elements )
                if ( element != element1 && element != element2 )
                {
                    // Si e1 < e2 et e2 < e, alors e1 < e
                    if ( table.Get( element2, element ) == valeur )
                    {
                        // Affectation de la valeur entre e1 et e
                        if ( Initialiser( table, element1, element, valeur, elements ) == false )
                            return false;
                    }
                }
 
            return true;
        }

Forcer les choix :

Code C# :

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
 
        static bool ForcerLesChoix( Table table, List<string> elements )
        {
            // Pour chaque élément
            foreach ( string element in elements )
            {
                bool continuer = true;
 
                // Tant qu'il y a au moins 2 autres éléments sans contrainte avec celui-ci
                while ( continuer )
                {
                    // Identifier les éléments sans contrainte (c'est à dire les ei tels que table[e, ei] = 0)
                    List<string> elementsSansContrainte = table.ElementsSansContrainte( element );
 
                    if ( elementsSansContrainte.Count > 1 )
                    {
                        // Affecter une valeur arbitraire entre e et le premier ei
                        if ( Initialiser( table, element, elementsSansContrainte[0], -1 , elements ) == false )
                            return false;
                    }
                    else
                        continuer = false;
                }
            }
 
            return true;
        }

Sinon

Une simple concaténation
l1 = a, bb, c, pp
l2 = a, r, l, pp
l3 = r, c , pp
->
a, bb, c, pp, a, r, l, pp, r, c , pp
suivie de l'élimination des doublons
ne suffit elle pas ?
(je suppose que le problème est possible, c'est à dire que on n'a pas
l1=a,b,..
l2= b,a,...)

Pourquoi pas, mais je dois dire que je ne comprends pas comment / selon quels critères tu élimines les doublons...

[Nebulix]

Pourquoi pas, mais je dois dire que je ne comprends pas comment / selon quels critères tu élimines les doublons...[/QUOTE]

a, bb, c, pp, a, r, l, pp, r, c , pp
a, bb, c, pp, a, r, l, pp, r, c , pp
a, bb, c, pp, r, l, pp, r, c , pp
a, bb, c, pp, r, l, r, c

Est-ce trop simple ? Quelles garanties as-tu que ton problème n'est pas insoluble comme je l' ai écrit plus haut ?

[Alikendarfen]

a, bb, c, pp, a, r, l, pp, r, c , pp
a, bb, c, pp, a, r, l, pp, r, c , pp
a, bb, c, pp, r, l, pp, r, c , pp
a, bb, c, pp, r, l, r, c

Est-ce trop simple ? Quelles garanties as-tu que ton problème n'est pas insoluble comme je l' ai écrit plus haut ?

... désolé, je ne vois toujours pas (quelles sont les règles ?)... d'autant que pp doit être en dernier

Sinon, dans ce problème, je pense qu'il n'y a pas de garantie de cohérence des listes : il faut donc tester la compatibilité des listes d'origine.

Mais ça serait bien que ffomnislash nous en dise un peu plus pour confirmer tout ça...

[Nebulix]

... désolé, je ne vois toujours pas (quelles sont les règles ?)... d'autant que pp doit être en dernier

Sinon, dans ce problème, je pense qu'il n'y a pas de garantie de cohérence des listes : il faut donc tester la compatibilité des listes d'origine.

Mais ça serait bien que ffomnislash nous en dise un peu plus pour confirmer tout ça...

Tu as raison, je suis allé trop vite.