相交集合，以使结果是一组具有共同唯一元素的集合

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次）。对于这种类型的问题，有更好的解决方案吗？

Answer 1

更新:不迭代任何集合，仅使用集合运算

该算法正在建设性地构建结果集，即每次看到新的源集时，我们都会修改现有的唯一元素集和/或添加新的元素集。

这个想法是，每个新集合都可以分为两部分，一部分是已经看到的值，另一部分是新的唯一值。对于第一部分，它被当前结果集进一步拆分为各种子集（最多 # 个已见源集的幂集）。对于每个这样的子集，它还分为两部分，一部分与新的源集相交，另一部分不相交。作业是更新每个类别的结果集。

就集合运算的复杂性而言，这应该是O(n*2^n).对于OP贴出的解决方案，我觉得复杂度应该是O(2^(2n)，因为< code>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]}