Союз всех перекрестных наборов

Question

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

В частности, это объекты Person, каждый со многими атрибутами. Мне нужно создать список «основных» наборов на основе нескольких уникальных идентификаторов, таких как SSN, DLN и т. Д.

Например, если Person A и Person B имеют одинаковый SSN, они создают набор i. Тогда, если Person B и C имеют один и тот же DLN, они создают набор ii. У лиц D и E есть один и тот же SSN, но он (и все другие идентификаторы) не соответствует ни одному из идентификаторов лиц A, B или C. После слияния всех пересекающихся подмножеств я получаю один набор с лицами A, B, C и другой набор с лицами D, E.

Вот psuedo-код для моего решения. Мне любопытно, если кто-то уже придумал более эффективный способ слияния всех возможных пересекающихся множеств. Имейте в виду, что ссылки между наборами могут быть X Лица длинными (то есть A соответствует B по SSN и B соответствует C по DLN и C соответствует D по SSN, а D соответствует E каким-либо другим идентификатором, приведет к Лицам A-E в одном наборе). Также предположим, что язык будет реализован в операциях с установленными операциями.

bigSetList = array of all of the uniq Sets 
fullyTested = false 
while (bigSetList.size() > 1) or (fullyTested is false) 
    foreach thisSet in bigSetList order by size desc 
     if count(sets that intersect with thisSet) > 0 
      newThisSet = thisSet 
      intersectingSets = [] 
      bigSetList.delete(thisSet) 
      foreach testSet in bigSetList 
       if thisSet.intersects(testSet) 
        newThisSet.addAll(testSet) 
        intersectingSets.push(testSetID) 
       end if 
      end 
      bigSetList.delete(intersectingSets) 
      bigSetList.push(newThisSet) 
      bigSetList.sort() 
      break 
     end if 
    end foreach 
    fullyTested = true // have looped through every set in the list and found 0 intersect partners 
end 

Answer 1

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

Наивно это можно решить, найдя все пары, которые совместно используют атрибут и объединяют пары вместе, которые имеют одинаковый партнер итеративно. Это было бы O (N^3) (N^2 для итерации по парам и до N отдельных наборов для определения принадлежности).

Вы также можете придумать эту проблему как определение connected component of a graph, где каждый объект и каждое уникальное значение атрибута являются узлом; каждый объект будет связан с каждым из его значений атрибутов. Настройка этого графика займет линейное время, и вы можете определить подключенные компоненты в линейном времени с помощью поиска по ширине или глубине.

Answer 2

Я предположил бы, что у вас есть относительно небольшой набор атрибутов для объекта Person (по сравнению с количеством объектов Person вы рассматриваете). Если вы хотите несколько раз перечеркнуть список объектов Person, вы можете взять Person, поместить его атрибуты в список известных возможных подключений и затем перейти к следующему Лицу. С каждым последующим Лицом вы видите, связано ли оно с каким-либо предыдущим соединением. Если это так, то вы добавляете его уникальные атрибуты к возможным соединениям. Вы должны иметь возможность обрабатывать все объекты Person за один проход. Возможно, у вас будут некоторые отключенные множества в результатах, поэтому, возможно, стоит изучить объекты Unconnected Person после создания первого графика.

Answer 3

Так что ваш пример коллекции может выглядеть следующим образом:

A { ss |-> 42, dl |-> 123 } 
B { ss |-> 42, dl |-> 456 } 
C { ss |-> 23, dl |-> 456 } 
D { ss |-> 89, dl |-> 789 } 
E { ss |-> 89, dl |-> 432 } 

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

Итерация 1. Первая коллекция становится единственным мульти-коллекция:

{A} { ss |-> [42], dl |-> [123] } 

Итерация 2. Слейте следующий сбор в т он первым, так как ПЛА уже присутствует:

{A,B} { ss |-> [42], dl |-> [123,456] } 

Итерация 3. Объединить снова, так как DLN уже есть:

{A,B,C} { ss |-> [23,42], dl |-> [123,456] } 

Итерация 4. Вставьте новый мульти-коллекции, так как нет матча:

{A,B,C} { ss |-> [23,42], dl |-> [123,456] } 
{D}  { ss |-> [89], dl |-> [789]  } 

Итерация 5. Объединить со вторым мульти сбора, так как ПЛА есть:

{A,B,C} { ss |-> [23,42], dl |-> [123,456] } 
{D,E} { ss |-> [89], dl |-> [432,789] } 

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

В общем случае, если существует n коллекций с постоянным числом k атрибутов, то этот алгоритм будет работать со временем O (nnk) = O (n). Наихудшее поведение выдается, если все значения атрибута различны. Когда между значениями атрибутов больше общего, время, необходимое для вставки и определения членства в наборах значений атрибутов (например, [23,42]), становится доминирующим фактором, поэтому наборы атрибутов должны быть эффективными.

Если вы используете optimal disjoint sets, то каждая операция поиска или слияния будет выполняться в амортизированном времени O (α (n)).

Таким образом, для каждой итерации будет не более n коллекций (ситуация, когда до сих пор не было объединено много коллекций). Чтобы интегрировать новую коллекцию в несколько коллекций, вам нужно будет выполнить операцию поиска по каждому набору множеств k, чтобы идентифицировать все сдвоенные коллекторы, которые должны быть объединены, что требует времени, ограниченного O (nk α (n)). Для слияния не более k коллекций, найденных таким образом, берется O (k α (n)).

Так что для всех итерации время ограничено O (п (пк α (п) + к α (п))) = О (п (пк α (п))) = О (п k α (n)) = O (n α (n)), так как k является константой.

Поскольку α (n) для всех практических целей также является константой, общее время ограничено O (n).

Answer 4

while (!people.isEmpty()) { 
    Person first = people.get(0); 
    people.remove(first); 
    Set<Person> set = makeSet(first); 
    for (Person person : people) { 
     for (Person other : set) { 
      if (person.isRelatedTo(other)) { 
       set.add(person); 
       people.remove(person); 
      } 
     } 
    } 
    sets.add(set); 
} 
for (Set<Person> a : sets) { 
    for (Set<Person> b : sets.except(a)) { 
     for (Person person : a) 
      for (Person other : b) { 
       if (person.isRelatedTo(other)) { 
        a.addAll(b); 
        b.clear(); 
        sets.remove(b); 
        break; 
       } 
      } 
    } 
} 

Answer 5

Во-первых, существует ли какая-то врожденная иерархия в идентификаторах и противоречат ли идентификаторы более высокого класса, отменяют один и тот же идентификатор более низкого класса? Например, если A и B имеют один и тот же SSN, B и C имеют один и тот же DLN, а C и D имеют тот же SSN, который не соответствует SSN A и B, означает ли это, что есть две группы или одна?

Предполагая, что противоречия не имеют значения, вы имеете дело с классами эквивалентности, как заявляет пользователь 57368 (неизвестный Google). Для классов эквивалентности люди часто обращаются к структуре Union-find. Что касается того, как выполнять эти объединения, это не сразу тривиально, потому что я предполагаю, что у вас нет прямой ссылки A-B, когда оба A и B имеют один и тот же SSN. Вместо этого наши наборы будут состоять из двух видов элементов. Каждая пара (attribute type, attribute value) = attribute является элементом. У вас также есть элементы, соответствующие object с. Когда вы перебираете список атрибутов для объекта, выполните объединение (object, attribute).

Одной из важных особенностей структуры данных поиска Union является то, что результирующая структура представляет собой набор. Он позволяет запросить «Что такое A в?» Если этого недостаточно, сообщите нам, и мы можем улучшить результат.

Но самая важная особенность заключается в том, что алгоритм имеет что-то похожее на поведение по постоянному времени для каждого объединения и операции запроса.