Trova duplicato in un elenco di un elenco di numeri interi

Se esegui il raggruppamento in base alla versione ordinata di ciascun elenco, quindi prendi la lunghezza di ciascun gruppo, è molto semplice da implementare. In Scala, questo è:

val groups = testData groupBy {_.sorted} mapValues {_.length}
groups foreach println
/* output:
   (List(3, 6, 8),1)
   (List(2, 4, 9),1)
   (List(1, 2, 3),2)
*/

Ovviamente, se hai i requisiti per ordinare o stampare la formattazione, ciò aggiunge complessità. Non conosco C #, ma LINQ ha GroupBy che dovrebbe funziona molto allo stesso modo.

• Ordina ogni volta
• Prima lunghezza di confronto
• Quindi confronta elemento per elemento
  Non appena un elemento non corrisponde, l'elenco non corrisponde a

Questo sito non riguarda il codice ma funziona

IEqualityComparer<List<int>> listComparer = new ListComparer();
testData.ForEach(l => l.Sort());
var distinctLists = testData
    .GroupBy(j => j, listComparer)
    .Select(group => new { List = group.Key, Count = group.Count() });

public class ListComparer : IEqualityComparer<List<int>>
{
    public bool Equals(List<int> x, List<int> y)
    {
        if (x.Count != y.Count)
            return false;
        for (int i = 0; i < x.Count; i++)
            if (x[i] != y[i]) return false;
        return true;
    }
    public int GetHashCode(List<int> x) => x.Count;
}

Approccio forza bruta:

• Prima ordina ogni elenco in TestData
• Quindi lessicographically ordina TestData (in modo che gli elenchi duplicati si seguano necessariamente l'un l'altro)
• Finalmente iterate su TestData . Per ogni lista, conta quanti elenchi sono uguali per trovare i duplicati (e se vengono trovati duplicati, saltarli nell'iterazione principale).

Approccio intelligente:

• Crea un elenco di in cui memorizzerai un checksum per ogni elenco in TestData insieme all'indice e alla relativa lunghezza e ordinalo per somma di controllo e lunghezza.
• scorrere attraverso questo elenco. Per ogni gruppo di oggetti consecutivi aventi lo stesso checksum e lunghezza, procedere come l'approccio forza bruta, ma solo per le liste corrispondenti (potenzialmente uguali).

Questo approccio si basa sul fatto che solo gli elenchi che hanno lo stesso checksum e la lunghezza potrebbero essere uguali, per ridurre il numero di elenchi da ordinare e confrontare.

Questo secondo approccio è più complesso da implementare ma ha il vantaggio di eseguire l'ordinamento e il confronto più costosi solo quando è veramente necessario. Potresti certamente adattare l'algoritmo per sostituire l'ordinamento con un confronto intelligente

Ecco una piccola implementazione del primo approccio, tra cui un elegante ordinamento lessicografico di elenchi :

    // Sort every list in the list 
    for (int i = 0; i < TestData.Count; i++) 
         TestData[i].Sort();

    // Order the list of lists using a lexicographic sort
    TestData.Sort((x, y) => {
        var result = x.Zip(y, Tuple.Create)
                       .Select(z => z.Item1.CompareTo(z.Item2))
                       .FirstOrDefault(k => k != 0);
        return result == 0 && !x.Any() ? -1 : result; 
    });
    var sorted = TestData; 

    // Iterating through the ordered list of list to spot the duplicates
    List<int> t=null;
    int cpt = 1;  
    foreach (var l in sorted)
    {
         if (t != null)  // do nothing for the very first list
         {
             // in all other cases, compare list with the previous one
             var a = t.SequenceEqual(l);
             if (a) // if it's the same, increment occurrence counter
                 cpt++;
             else   // if not, show the duplicates and restart counting
             {
                 Console.Write("{0} x ", cpt);
                 WriteList(t);
                 cpt = 1;
             }
         }
         t = l; 
     }
     if (t!=null)  // process the last element outside the loop
     {
         Console.Write("{0} x ", cpt);
         WriteList(t);
     }

Con il seguente test input:

    List<List<int>> TestData
        = new List<List<int>>  { new List<int> { 1, 2, 3 },
                                 new List<int> { 1, 8, 2 },
                                 new List<int> { 2, 1, 3 },
                                 new List<int> { 9, 2, 4 } };

produrrà l'output atteso:

    2 x  1 2 3
    1 x  1 2 8
    1 x  2 4 9

1. È necessario definire cosa significa che un elenco è duplicato. Sembra che non ti interessi per l'ordine in modo che {1, 2, 3} sia un duplicato di {2, 1, 3}, ma ignori anche i numeri duplicati in modo che {1, 2, 3} sia un duplicato di {2 , 1, 1, 3}?

2. Scrivi un IEqualityComparer usando la definizione per l'uguaglianza che decidi tu. (Ad esempio confrontare come set o come liste ordinate)

3. Usa GroupBy con il comparatore di uguaglianza per raggruppare gli elenchi simili, quindi puoi ottenere il Count dei duplicati in ciascun gruppo.

    testData.forEach(list -> list.sort((o1, o2) -> o1 - o2));
    testData.stream()
    .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
    .forEach((integers, aLong) -> System.out.printf("%dx) %s\n", aLong, integers));
/*
   OUTPUT:
   2x) [1, 2, 3]
   1x) [3, 6, 8]
   1x) [2, 4, 9]
*/