Объединение множеств, которые имеют хотя бы один общий элемент

Question

Возможный дубликат:
Python: простое объединение списков на основе пересечений

Я пытаюсь классифицировать объекты. Каждый объект идентифицируется уникальным идентификатором, который называется id, Так что моя логика классификации выглядит следующим образом. Сначала я готовлю список объектов, а затем функция классификации берет 2 объекта за раз и возвращает frozenset содержащие их id, Так что если object1 а также object5 находятся в той же категории frozenset(id1,id5) возвращается Теперь я продолжаю добавлять эти заморозки в набор, так что в итоге у меня есть такой набор

matched_set=(
             frozenset(id1,id2),
             frozenset(id9,id3),
             frozenset(id9,id2),
             frozenset(id24,id22),
             frozenset(id1,id23),
             frozenset(id25,id24),
             frozenset(id30,id24)
            )

Теперь, потому что объекты с id1 а также id2 находятся в той же категории, объекты с id9 а также id3 находятся в той же категории, объекты с id9 а также id2 находятся в той же категории, объекты с id1,id2,id3,id9 должен быть в той же категории. Так что у меня должен быть такой набор set(id1,id2,id3,id9)Может кто-нибудь предоставить алгоритм для этого? Спасибо

Answer 1

Похоже, вы ищете структуру данных с несвязным набором данных.

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

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

Обычный метод состоит в представлении каждой категории в виде обратного дерева: каждый идентификатор имеет parent ссылка, но нет дочерних ссылок. "Представительский элемент" является корнем дерева, к которому легко обращаться, следуя по родительским ссылкам. Обновление требует поиска корня деревьев обоих идентификаторов и (если они различаются) слияния деревьев, делая один корень родителем другого.

Добавив пару простых оптимизаций (запросы "сворачивают" путь запроса, чтобы указать непосредственно на корень, а обновления всегда выбирают корень самого глубокого дерева в качестве родителя слияния), этот алгоритм становится чрезвычайно эффективным и работает в режиме "почти-O". (1)"Амортизированное время.

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