交集，结果是一组具有彼此唯一元素的集合

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 次）。针对这种问题，是否有更好的解决方案呢？

- Lindenk

Answer 1

更新：不迭代任何集合，只使用集合操作。

这个算法是通过构建结果集来完成的，也就是说，我们每次看到一个新的源集合时，都会修改现有的唯一元素集合和/或添加新的集合。

这个想法是，每个新的集合都可以分成两部分，一部分是已经见过的值，另一部分是新的唯一值。对于第一部分，它进一步被当前结果集拆分成各种子集（最多是已见过的源集合的幂集数）。对于每个这样的子集，它也分为两部分，一部分与新的源集合相交，另一部分则没有。任务是更新每个类别的结果集。

关于集合操作的复杂度，应该是O(n*2^n)。对于OP发布的解决方案，我认为复杂度应该是O(2^(2n))，因为len(resulting_sets)在最坏情况下有2^n个元素。

最初的回答：

该算法通过构建结果集来实现，即每次查看新的源集合时，都会修改现有的唯一元素集合和/或添加新的集合。每个新的集合可以分成两部分，一部分是已经见过的值，另一部分是新的唯一值。对于第一部分，它被当前结果集拆分成各种子集（最多是已见过的源集合的幂集数）。对于每个这样的子集，它也分为两部分，一部分与新的源集合相交，另一部分则没有。任务是更新每个类别的结果集。关于集合操作的复杂度，应该是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 & 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(sets))，在最坏情况下为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]}

- lnyng

---

谢谢！但不幸的是，我无法实际循环遍历每个元素。这些集合本身包含多达~2^64个元素，并通过排除集和元素范围来跟踪它们，而不是每个单独的元素。其中一个要点说明了约束条件。 - Lindenk

@Lindenk 你是在以集合操作的数量来计算复杂度吗？请注意，集合交集的时间复杂度为O(min(M,N))，而成员测试的时间复杂度则是O(1)，都是以元素数量为基础的。 - lnyng

哎呀，你说得对。不知道为什么我以为幂集是n^2，实际上它是2^n。哇，这样情况更糟了。 - Lindenk