Поиск дубликатов в списке списка

Вы также можете попробовать вероятностные алгоритмы, если дубликаты встречаются очень редко или очень часто. например a фильтр цветения

, если все они однозначные и имеют одинаковое количество элементов, вы можете сложить их вместе, так что первым будет 123456 и проверьте, совпадают ли числа.

тогда у вас будет список {123456, 123456, 142456, 325164}

, который легче проверять на дубликаты, если отдельных членов может быть больше 10, вам придется его изменить.

Edit: добавлен пример кода, можно оптимизировать, это просто быстрый пример, объясняющий, что я имел в виду.

for(int i = 0; i< list.length; i++)
{
    List<int> tempList = list[i];
    int temp = 0;
    for(int j = tempList.length - 1;i > = 0; j--)
    {
        temp = temp * 10 + tempList[j];
    }
    combinded.add(temp);
}

for(int i =0; i< combined.length; i++)
{
    for(int j = i; j < combined.length; j++)
    {
        if(combined[i] == combined[j])
        {
            return true;
        }
    }
}
return false;

Ознакомьтесь с C # 3.0: необходимость возврата дубликатов из списка <> показывает, как вернуть дубликаты из списка.

Пример с этой страницы:

var duplicates = from car in cars
             group car by car.Color into grouped
             from car in grouped.Skip(1)
             select car;

Вам придется выполнить итерацию по каждому индексу каждого списка по крайней мере один раз, но потенциально вы можете ускорить процесс, создав пользовательскую хеш-таблицу, чтобы вы могли быстро отклонять неповторяющиеся списки. без необходимости делать сравнения по элементам.

Алгоритм:

Create a custom hashtable (dictionary: hash -> list of lists)
For each list
  Take a hash of the list (one that takes order into account)
  Search in hashtable
  If you find matches for the hash
    For each list in the hash entry, re-compare the tables
      If you find a duplicate, return true
  Else if you don't find matches for the hash
    Create a temp list
    Append the current list to our temp list
    Add the temp list to the dictionary as a new hash entry
You didn't find any duplicates, so return false

Если у вас есть достаточно сильный алгоритм хеширования для ваших входных данных, вам, возможно, даже не придется выполнять подсравнения, поскольку не будет конфликтов хэшей.

У меня есть пример кода. Недостающие биты:

• Оптимизация, так что мы делаем поиск в словаре только один раз для каждого списка (для поиска и вставки). Возможно, для этого придется создать свой собственный класс Dictionary/Hash Table?
• Лучший алгоритм хэширования, который вы найдете, профилируя их кучу по своим данным.

Вот код:

public bool ContainsDuplicate(List<List<int>> input)
{
    var encounteredLists = new Dictionary<int, List<EnumerableWrapper>>();

    foreach (List<int> currentList in input)
    {
        var currentListWrapper = new EnumerableWrapper(currentList);
        int hash = currentListWrapper.GetHashCode();

        if (encounteredLists.ContainsKey(hash))
        {
            foreach (EnumerableWrapper currentEncounteredEntry in encounteredLists[hash])
            {
                if (currentListWrapper.Equals(currentEncounteredEntry))
                    return true;
            }
        }
        else
        {
            var newEntry = new List<EnumerableWrapper>();
            newEntry.Add(currentListWrapper);
            encounteredLists[hash] = newEntry;
        }
    }

    return false;
}

sealed class EnumerableWrapper
{
    public EnumerableWrapper(IEnumerable<int> list)
    {
        if (list == null)
            throw new ArgumentNullException("list");
        this.List = list;
    }

    public IEnumerable<int> List { get; private set; }

    public override bool Equals(object obj)
    {
        bool result = false;

        var other = obj as EnumerableWrapper;
        if (other != null)
            result = Enumerable.SequenceEqual(this.List, other.List);

        return result;
    }

    public override int GetHashCode()
    {
        // Todo: Implement your own hashing algorithm here
        var sb = new StringBuilder();
        foreach (int value in List)
            sb.Append(value.ToString());
        return sb.ToString().GetHashCode();
    }
}

Вот потенциальная идея (предполагается, что значения являются числовыми):

Реализовать компаратор, который умножает каждый член каждой коллекции на его индекс, а затем суммирует все это:

Value:    0  5  8  3  2  0  5  3  5  1
Index:    1  2  3  4  5  6  7  8  9  10
Multiple: 0  10 24 12 10 0  35 24 45 10

Контрольная сумма члена: 170

Итак, вся «строка» имеет номер, который меняется в зависимости от членов и порядка. Быстро вычислять и сравнивать.

Что-то вроде этого даст вам правильные результаты:

List<List<int>> list = new List<List<int>>(){
  new List<int>() {0 ,1 ,2, 3, 4, 5, 6 },
  new List<int>() {0 ,1 ,2, 3, 4, 5, 6 },
  new List<int>() {0 ,1 ,4, 2, 4, 5, 6 },
  new List<int>() {0 ,3 ,2, 5, 1, 6, 4 }
};

list.ToLookup(l => String.Join(",", l.Select(i => i.ToString()).ToArray()))
    .Where(lk => lk.Count() > 1)
    .SelectMany(group => group);

Если вы не занимаетесь серьезно тяжелой работой, возможно, вам подойдет следующий простой код:

var lists = new List<List<int>>()
{
   new List<int>() {0 ,1, 2, 3, 4, 5, 6 },
   new List<int>() {0 ,1, 2, 3, 4, 5, 6 },
   new List<int>() {0 ,1, 4, 2, 4, 5, 6 },
   new List<int>() {0 ,3, 2, 5, 1, 6, 4 }
};

var duplicates = from list in lists
                 where lists.Except(new[] { list }).Any(l => l.SequenceEqual(list))
                 select list;

Очевидно, что вы могли бы повысить производительность, если бы вручную настроили алгоритм так, чтобы вам не приходилось просматривать списки. каждой итерации, но есть что сказать о написании декларативного, более простого кода.

(Кроме того, благодаря удивительности LINQ®, добавлению вызова .AsParallel() к приведенному выше коду, алгоритм будет работать на нескольких ядрах, таким образом, работая потенциально быстрее, чем сложные, настраиваемые вручную решения, упомянутые в этом нить.)

Как насчет того, чтобы написать свой собственный компаратор списков:

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> obj)
     {
        return base.GetHashCode();
     }
}

а затем просто:

var nonDuplicatedList = list.Distinct(new ListComparer());
var distinctCount = nonDuplicatedList.Count();

Есть здесь уже есть ряд хороших решений, но я считаю, что это будет работать быстрее всех, если только не будет какой-то структуры данных, о которой вы нам еще не рассказали.

• Создайте карту из целочисленного ключа в список и карту из ключа в List>
• Для каждого List вычислите хэш, используя некоторый простой функция вида (...((x0)*a + x1)*a + ...)*a + xN), которую можно вычислить рекурсивно; a должно быть чем-то вроде 1367130559 (т. е. некоторым большим простым числом, случайно не близким ни к какой интересующей степени 2.
• Добавьте хэш и список, из которого он получен, как пару ключ-значение, если его не существует. Если он существует, посмотрите на второй карте. Если на второй карте есть этот ключ, добавьте новый List к накапливающемуся списку. Если нет, возьмите List, который вы искали на первой карте, и List, которые вы тестировали, и добавьте новую запись во вторую карту, содержащую список этих двух элементов.
• Повторяйте, пока не пройдете весь первый список.Теперь у вас есть хэш-карта со списком потенциальных коллизий (вторая карта) и хэш-карта со списком ключей (первая карта).
• Повторите вторую карта.Для каждой записи возьмите List> и отсортируйте его лексикографически. Теперь просто выполните сравнения на равенство, чтобы подсчитать количество разных блоков.
• Общее количество элементов равно длине исходного списка.
• Количество отдельных элементов равно размеру вашей первой хэш-карты плюс сумма (количество блоков - 1) для каждой записи во второй хэш-карте.
• Ваше количество повторяющихся элементов равно разности этих двух чисел (и при желании вы можете узнать множество других вещей).

Если у вас есть N неповторяющихся элементов и M элементов, которые дублируются из набора из K элементов, вам потребуется O(N+M+2K) для создания исходных хэш-карт, в самом худшем случае O (M log M), чтобы выполнить сортировку (и, вероятно, больше похоже на O (M log (M/K))) и O (M), чтобы выполнить окончательный тест на равенство.