Союз всех пересекающихся множеств

Question

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

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

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

Вот псевдо-код для моего решения. Мне любопытно, если кто-нибудь уже придумал более эффективный способ объединения всех возможных пересекающихся множеств. Имейте в виду, что связи между наборами могут иметь длину X Persons (т.е. A соответствует B по SSN, а B соответствует C по DLN, а C соответствует D по SSN, а D соответствует E по некоторому другому идентификатору, что приведет к Persons 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 отдельных наборов для определения принадлежности).

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

Answer 2

Во-первых, существует ли некоторая внутренняя иерархия в идентификаторах, и противоречивые идентификаторы более высокого сорта отменяют один и тот же идентификатор более низкого сорта? Например, если 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-find является то, что результирующая структура представляет собой набор. Это позволяет вам спросить "Какой набор А в?" Если этого недостаточно, сообщите нам, и мы сможем улучшить результат.

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

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. Объедините следующую коллекцию с первой, поскольку SSN уже существует:

{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. Объединение со вторым мультиколлекцией, поскольку там есть SSN:

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

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

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

Если вы используете оптимальные непересекающиеся множества , то каждая операция поиска или слияния будет выполняться за амортизированное время O (& alpha; (n)).

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

Таким образом, для всей итерации время ограничено O (n (nk & alpha; (n) + k ² & alpha; (n))) = O (n (nk & alpha; (n))) = O (n ² k & alpha; (n)) = O (n ² & alpha; (n)), поскольку k является константой.

Поскольку & alpha; (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

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