python-3.x - 找到q-松弛交集的算法或Python函数？

Question

我正在寻找一种“更快”的方法来查找集合列表的q-relaxed 交集。我目前已经实现了以下 Python 函数，但速度很慢。我希望这适用于约 100 套和 q=10。有什么聪明的主意吗？

def relaxed_intersection(*sets, q=0):
    """
    This function finds the q-relaxed intersection set of the sets supplied in
    *sets as a list.
    We first find the intersection of subsets formed by leaving q sets out and
    then find the union of these intersetions.
    """
    import itertools
    n = len(sets)
    #form subsets leaving q sets out
    combinations = list(itertools.combinations(sets, n-q))

    #find the intersection of all the subsets
    intersections = [set() for i in range(len(combinations))]
    for i, comb in enumerate(combinations):
        intersections[i] = set.intersection(*comb)

    #find the union of all the intersections
    q_relaxed_set = set.union(*intersections)

    return q_relaxed_set

标签： python-3.xset-theory

Answer 1

只需检查每个元素是否至少是n - q集合的一部分。

from collections import Counter

def relaxed_intersection(*sets, q=0):
    """
    This function finds the q-relaxed intersection set of the sets supplied in
    *sets as a list.
    """

    counter = Counter(x for s in sets for x in set(s))
    n = len(sets)
    return {x for x, c in counter.items() if c >= n - q}