Discussion :

[Flow_75]

Bonjour,

Voilà j'ai N listes contenant des éléments de type T.

Je cherche une méthode correctement optimisée permettant de trouver tous les éléments
se trouvant dans au moins deux listes.

J'ai un peu de difficultés dans ce genre d'algorithmes.
Pourriez vous m'aider ?
Merci.
Flow

[Noxen]

Voici une approche assez simple en utilisant LinQ. Ce n'est pas forcément totalement optimisé mais ça de donnera une base de départ à laquelle comparer d'autres options au niveau performance :

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
namespace AtLeastTwo
{
    internal class Program
    {
        static void Main(string[] args)
        {
            var l1 = new[] { new Item("a"), new Item("b"), new Item("c") };
            var l2 = new[] { new Item("b"), new Item("d"), new Item("e") };
            var l3 = new[] { new Item("d"), new Item("f"), new Item("f") };
            var listOfLists = new[] { l1, l2, l3 };
 
            var comparer = new ItemEqualityComparer();
 
            var result = listOfLists
                .SelectMany(l => l.Distinct(comparer)) // aplanir les listes en ne conservant pas les doublons de chaque liste
                                                       // (distinct n'est pas nécessaire si les éléments sont déjà uniques)
                .GroupBy(i => i, comparer) // regrouper les items identiques
                .Where(g => g.Count() > 1) // ne conserver que ceux qui appraissent plus d'une fois (maintenant on cherche les doublons)
                .Select(g => g.Key) // garder l'item
                .ToArray(); // exécuter
 
            Console.WriteLine("[");
            foreach (var s in result)
            {
                Console.WriteLine(s);
            }
            Console.WriteLine("]");
 
            Console.ReadLine();
        }
    }
 
    internal class Item
    {
        public Item(string value)
        {
            Value = value;
        }
 
        public string Value { get; }
 
        public override string ToString() => Value;
    }
 
    internal class ItemEqualityComparer : IEqualityComparer<Item>
    {
        public bool Equals(Item x, Item y) => x?.Value == y?.Value;
 
        public int GetHashCode(Item obj) => obj?.Value?.GetHashCode() ?? 0;
    }
}

Pour optimiser il faut partir du principe que le code qui prend le moins de temps c'est celui qui n'est pas exécuté, donc ça consistera à limiter autant que possible les comparaisons par exemple en supprimant les items déjà sélectionnés. Mais avec ce genre de problème il reste difficile de sortir d'une complexité quadratique.

[Flow_75]

D'accord !

Merci de ton aide !

[WaterTwelve21]

Bonjour,

La réponse de Noxen est trés bonne en plus d'être correct, cela m'a fait aussitôt penser que j'ai une méthode d'extention qui a ce rôle dans un de mes projets.

Je la pose içi, ça pourrai en intéresser certains.

C'est à un poil prés le même code que Noxen.

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
 
        /// <summary>
        /// Méthode qui récupère les éléments présents dans plusieurs listes selon le nombre d'occurence
        /// </summary>
        /// <typeparam name="T">le type des éléments</typeparam>
        /// <param name="listOfLists">la liste de listes</param>
        /// <param name="nbOccurence">le nombre d'occurences nécéssaire</param>
        /// <param name="bAtLeast">précision du filtre, si vrai on recherche "au moins", sinon on recherche avec exactitude</param>
        /// <param name="comparer">le comparateur d'égalité, qu'es-ce qui défini que deux éléments soit identiques ?</param>
        /// <returns></returns>
        public static IEnumerable<T> GetElementsByOccurence<T>(this IEnumerable<IEnumerable<T>> listOfLists,int nbOccurence,bool bAtLeast,IEqualityComparer<T> comparer)
        {
            if (!listOfList.Any())
                return null;
 
            return listOfLists
                   .SelectMany(ls => ls)
                   .GroupBy(item => item, comparer)
                   .Where(group =>  (bAtLeast) ? group.Count() >= nbOccurence : group.Count() == nbOccurence)
                   .Select(group => group.Key);
        }

Je pense rajouter le Distinct() pour les raisons que cite Noxen, bien qu'avoir des listes avec des doublons j'aime pas mais ca peut arriver.

Merci !

[wallace1]

euhhh rien à dire vous êtes au top les gars.

@Noxen : belle approche commentée qui plus est.