объединение/пересечение 2 наборов, где каждый набор определяется его подмножествами

Question

Мы знаем определение каждого множества из объединения других множеств.

Например

А = В объединение {1,2}

В = С объединением Д

С = {5,6}

D = {5,7}

Е = {4}

тогда А = {1,2,5,6,7}

Объединение E = {1,2,4,5,6,7}

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

Answer 1

Итак, у вас есть неизменная иерархия союзов сменяющих друг друга наборов? И вы, как в вашем примере, интересуетесь только значением одного набора?

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

Чтобы отказаться от перекомпоновки профсоюзов при изменении набора листьев, вы можете отслеживать для каждого элемента количество установленных в нем наборов. Это может быть быстро обновлено, если набор листьев изменяется, и те, которые не требуются, смотрят на любые неизменные наборы листьев. Тогда те элементы с частотным числом> 0 в настоящее время находятся в союзе.

Answer 2

Возможно, вы ищете какую-то структуру данных disjoint set?

Answer 3

Несколько вопросов об этом случае.

Первый вопрос: как долго длится этот «скрипт»/«программа»? В случае, если это не слишком долго, вполне может быть хорошим вариантом просто сохранить предыдущие союзы и проверить кеш перед выполнением действия объединения. В наши дни память не так дорого :).

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