组合排列集

Question

我有2组集合，我需要将它们组合的所有排列（如在并集中）放入一个集合中，使其中没有2个集合包含重复元素（可以假设每个父集合本身没有具有重复元素的集合），而我只能移除第二级集合，而不能移除元素本身，例如：

[(a,b),(c),(d)] and [(a),(b,c),(e)]

会让我：

^{pr2}$

一个父集合中的一个集合可以给我另一个父集合中不兼容的集合的子集（即，包含一个或多个公共元素），将这些集合保留在第二个集合中会给我一个新的集合子集，我可以从第一个集合中移除，依此类推。。递归地运行这个并检查重复是相当耗时的。。。在

有没有更好的方法来解决这个问题？我能用什么工具？（目前在python中执行此操作）

另请注意，这是我的意思的一个小代码示例，我并不是要修复bug，只是要求更简洁的方法：

def combine(S1, S2, incompatible_set, parent_set_pairs):

    new_S2 = None
    new_incompatible_sets = set()

    for s2 in S2:
        if incompatible_set & s2:
            new_incompatible_sets.add(s2)
            if not S2:
                S2 = S2.copy()
            new_S2.remove(s2)
    parent_set_pairs.add((S1, new_S2)) # here it should look for a new incompatible set in S1 and apply the function again..
    for new_incompatible_set in new_incompatible_sets:
        new_parent_set_pairs = combine(S2, S1, new_incompatible_set,
                                 parent_set_pairs)
        for pair1 in new_parent_set_pairs:
            for pair2 in parent_set_pairs:
                if pair1[0]|pair1[1] not in pair2[0]|pair2[1]
            parent_set_pairs.add(new_parent_set_pairs)

    return parent_set_pairs

Answer 1

这是一种基于itertools的方法，它采用两个不相交集的列表，并返回从这两个列表中提取的所有不相交集的最大组合，但这些组合中的集合是不相交的：

from itertools import combinations

def maxDisjoints(A,B):
    n = len(A)
    combos = set()
    for i in range(n+1):
        for partA in combinations(A,i):
            A_covered = set().union(*partA)
            filteredB = [s for s in B if A_covered & s == set()]
            B_covered = set().union(*filteredB)
            filteredA = [s for s in A if B_covered & s == set()]
            #filteredA is a superset of partA
            #freeze and record:
            combos.add(tuple(frozenset(s) for s in filteredA + filteredB))
    #unfreeze and return as list of lists of sets:       
    return [[set(f) for f in t] for t in combos]

要测试它：

^{pr2}$

输出：

[{'c'}, {'d'}, {'a'}, {'e'}]
[{'d'}, {'a'}, {'b', 'c'}, {'e'}]
[{'b', 'a'}, {'c'}, {'d'}, {'e'}]

作为一个技术上的麻烦，集合和列表都不是散列的，所以不可能维护一组集合列表来过滤冗余（因为算法多次生成相同的最大组合）。因此，我不得不将集合列表转换为冻结集合的元组来临时记录它们，但最后却颠倒了这个过程。在

这是一种暴力手段。它遍历A的所有2^n个子集，以唯一可能的方式将每个子集扩展为最大组合。如果a和B的大小不一致，请先传递两个列表中较短的一个（或调整代码，使其自动执行此操作）。这种方法对于规模较小的收藏品来说是合理的，但规模不大。我怀疑这个问题本身是NP难的，所以你期望的效率是有限的（这并不是说这个算法是最优的）。在