Объединение всех пересекающихся множеств

Question

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

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

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

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

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

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

Answer 3

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 4

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

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

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

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

Answer 5

Итак, ваш пример коллекции может выглядеть так:

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(α(n)).

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

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

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