Блог

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

 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 раз). Есть ли лучшее решение для такого типа проблем?

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

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

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

Для сложности с точки зрения операций с множествами это должно быть O (n * 2 ^ n). Для решения, опубликованного OP, я думаю, сложность должна быть 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 amp; 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]}