Пересекающиеся множества, так что результатом является набор множеств с коллективно уникальными элементами

Question

Допустим, у меня есть следующие наборы:

X -> {1, 2, 3}  
Y -> {1, 4, 7}  
Z -> {1, 4, 5}

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

A -> {2, 3}: {X}
B -> {7}:    {Y}
C -> {5}:    {Z}
D -> {4}:    {Y, Z}
E -> {1}:    {X, Y, Z}

Чтобы решить проблему, должны быть выполнены следующие условия:

• Для каждогоначальный набор, каждый элемент будет в результирующем наборе, созданном пересечением максимального числа начальных наборов
• То есть каждый элемент в начальном наборе должен быть точно в одном результирующем наборе
• Наборы реально бесконечны, то есть обход всех допустимых элементов невозможен, но операции набора хороши
• Все результирующие наборы, не содержащие элементов, можно игнорировать

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

resulting_sets = {}
for sets in powerset(S):
  s = intersection(sets)
  for rs in resulting_sets.keys():
    s -= rs

  if not s.empty():
    resulting_sets[s] = sets # realistically some kind of reference to sets

Конечно, вышеупомянутое довольно неэффективно при O (n ^ 2log (n)) O (2 ^ n * 2 ^ (n / 2)) операций над множествами (и для моих целей это может выполняться до n ^ 2 раз заlready).Есть ли лучшее решение для этого типа проблемы?

Answer 1

ОБНОВЛЕНИЕ : без итерации какого-либо набора, используются только операции набора

Этот алгоритм строит наборы результатов конструктивно, то есть мы модифицируем существующие уникальные наборы элементов и / или добавляем новые каждый размы видим новый исходный набор.

Идея состоит в том, что каждый новый набор можно разбить на две части, одну с уже увиденными значениями, а другую с новыми уникальными значениями.Для первой части он далее делится на различные подмножества (до # набора мощности видимых исходных наборов) текущими наборами результатов.Для каждого такого подмножества оно также разбивается на две части: одна пересекается с новым исходным набором, а другая - нет.Задача состоит в том, чтобы обновить наборы результатов для каждой из этих категорий.

Для сложности с точки зрения операций над множествами это должно быть O (n * 2 ^ n).Для решения, опубликованного ОП, я думаю, что сложность должна быть O (2 ^ (2n)), потому что len(resulting_sets) имеет до 2 ^ n элементов в худшем случае.

def solution(sets):
    result_sets = [] # list of (unique element set, membership) tuples
    for sid, s in enumerate(sets):
        new_sets = []
        for unique_elements, membership in result_sets:
            # The intersect part has wider membership, while the other part
            # has less unique elements (maybe empty).
            # Wider membership must have not been seen before, so add as new.
            intersect = unique_elements & s
            # Special case if all unique elements exist in s, then update
            # in place
            if len(intersect) == len(unique_elements):
                membership.append(sid)
            elif len(intersect) != 0:
                unique_elements -= intersect
                new_sets.append((intersect, membership + [sid]))
            s -= intersect
            if len(s) == 0:
                break
        # Special syntax for Python: there are remaining elements in s
        # This is the part of unseen elements: add as a new result set
        else:
            new_sets.append((s, [sid]))
        result_sets.extend(new_sets)
    print(result_sets)

sets = [{1, 2, 3}, {1, 4, 7}, {1, 4, 5}]
solution(sets)

# output:
# [(set([2, 3]), [0]), (set([1]), [0, 1, 2]), (set([7]), [1]), (set([4]), [1, 2]), (set([5]), [2])]

-------------- оригинальный ответ ниже ---------------

Идея состоит в том, чтобы найти «членство» каждого уникального элементат.е. к каким наборам он принадлежит.Затем мы создаем словарь для группировки всех элементов по их принадлежности, генерируя запрошенные множества.Сложность O (n * len (множеств)) или O (n ^ 2) в худшем случае.

def solution(sets):
    union = set().union(*sets)
    numSets = len(sets)
    numElements = len(union)
    memberships = {}
    for e in union:
        membership = tuple(i for i, s in enumerate(sets) if e in s)
        if membership not in memberships:
            memberships[membership] = []
        memberships[membership].append(e)
    print(memberships)

sets = [{1, 2, 3}, {1, 4, 7}, {1, 4, 5}]
solution(sets)

# output:
# {(0, 1, 2): [1], (1, 2): [4], (0,): [2, 3], (1,): [7], (2,): [5]}