查找所有最大子集的高效算法

  • Z时代
  • 2024-01-10
  • 分类：问答

我有一组唯一的集合（表示为位掩码），并希望消除所有元素，这些元素是另一个元素的适当子集。例如：

input = [{1, 2, 3}, {1, 2}, {2, 3}, {2, 4}, {}]
output = [{1, 2, 3}, {2, 4}]

我无法为此找到标准算法，甚至无法找到该问题的名称，因此我称其为“最大子集”是因为没有其他任何东西。这是一个O（n ^

2）算法（在Python中为具体起见），假设is_subset_func为O（1）：1

def eliminate_subsets(a, cardinality_func, is_subset_func):
    out = []
    for element in sorted(a, reverse=True, key=cardinality_func):
        for existing in out:
            if is_subset_func(element, existing):
                break
        else:
            out.append(element)
    return out

是否有更有效的算法，希望O（n log n）或更佳？

1 对于恒定大小的位掩码，正如我的情况is_subset_func一样element & existing == element，它是just

，它在恒定时间内运行。

回答：

假设您标记了所有输入集。

A={1, 2, 3}, B={1, 2}, C={2, 3}, D={2, 4}, E={}

现在构建中间集，在Universe中每个元素一个，包含其中出现的集的标签：

1={A,B}
2={A,B,C,D}
3={A,C}
4={D}

现在，对于每个输入集，计算其元素的所有标签集的交集：

For A, {A,B} intesect {A,B,C,D} intersect {A,C} = {A}   (*)

如果相交包含集合本身以外的其他标签，则它是该集合的一个子集。这里没有其他元素，因此答案是否定的。但，

For C, {A,B,C,D} intersect {A,C} = {A,C}, which means that it's a subset of A.

此方法的成本取决于集合的实现。假设位图（如您所暗示）。假设有n个最大大小为m和| U |的输入集。宇宙中的物品。然后，中间集构造产生| U

|。大小为n位的集合，因此有O（| U | n）时间来初始化它们。设置这些位需要O（nm）时间。(*)如上计算每个交叉点需要O（mn）; 全部为O（mn

^ 2）。

将所有这些放在一起，我们得到O（| U | n）+ O（nm）+ O（mn ^ 2）= O（| U | n + mn ^

2）。使用相同的约定，您的“所有对”算法为O（| U | ^ 2 n ^ 2）。由于m <= | U

|，因此该算法渐近更快。在实践中也可能会更快，因为没有详尽的簿记来添加恒定因素。

OP询问是否存在该算法的在线版本，即，当输入集一个接一个到达时，最大集的集合可以递增地维护的算法。答案似乎是肯定的。中间集可以快速告诉我们新集是否是已经看到的

集的子集 。但是如何快速判断它是否是 超集 ？而且，如果是这样，哪些现有最大集？在这种情况下，那些最大集不再是最大集，必须用新的替换。

关键是要注意，iff A的超集是的子集（“滴答”表示集合补码）。B``A'``B'

遵循这一灵感，我们像以前一样维护中间集。当新的输入集S到达时，请执行上述相同的测试：I(e)将其作为输入元素的中间集e。然后这个测试是

For X = \intersect_{e \in S} . I(e), |X| > 0

（在这种情况下，它大于零而不是上面的一个，因为它还S没有进入I。）如果测试成功，则新集合是现有最大集合的（可能不正确）子集，因此可以将其丢弃。

否则，我们必须添加S为新的最大集，但是在执行此操作之前，请先计算：

Y = \intersect_{e \in S'} . I'(e) = ( \union_{e \in S'} . I(e) )'

再次将“勾号”设置为补码。联合形式可能会更快地计算出来。Y包含已被取代的最大集S。必须将它们从最大集合和中删除I。最后添加S为最大集并I使用S元素进行更新。

让我们通过示例进行研究。当A到达时，我们把它添加到I和有

1={A}  2={A}  3={A}

当B到达时，我们发现X = {A} intersect {A} =

{A}，所以扔B走，继续。也会发生同样的情况C。当D到达时，我们发现X = {A} intersect {} = {}，如此继续Y =

I'(1) intersect I'(3) = {} intersect

{}。这正确地告诉我们，最大集合A不包含在中D，因此没有要删除的内容。但必须将其添加为新的最大集，并I成为

1={A}  2={A,D}  3={A}  4={D}

E原因的到来没有改变。然后摆放一套新的F={2, 3, 4, 5}。我们发现

X = {A} isect {A,D} isect {A} isect {D} isect {}

所以我们不能F丢掉 继续

Y = \intersect_{e in {1}} I'(e) = I'(1) = {D}

这说明我们D是的子集F，因此在F添加时应将其丢弃，留下

1={A} 2={A,F} 3={A,F} 4={F} 5={F}

由于算法的在线性质，补数的计算既棘手又不错。输入补语的Universe只需要包含到目前为止看到的输入元素。中间集合的Universe仅由当前最大集合中的集合标签组成。对于许多输入流，此集合的大小将随着时间的推移而稳定或减小。

我希望这是有帮助的。

这里工作的一般原则是一个强有力的想法，经常在算法设计中大量出现。这是反向映射。每当您发现自己进行线性搜索以查找具有给定属性的商品时，请考虑从该属性构建到商品的地图。构造此地图通常很便宜，而且可以大大减少搜索时间。最主要的示例是排列图p[i]，它告诉您i排列数组后，第th个元素将占据什么位置。如果你需要寻找的是结束了在给定位置的项目a，您必须搜索p的a，线性时间的操作。在另一方面，逆映射pi，从而pi[p[i]]

== i需要不再计算比做p（所以它的成本“隐藏的”），但pi[a] 在恒定时间内产生所需的结果。

import collections
import operator
from functools import reduce # only in Python 3
def is_power_of_two(n):
    """Returns True iff n is a power of two.  Assumes n > 0."""
    return (n & (n - 1)) == 0
def eliminate_subsets(sequence_of_sets):
    """Return a list of the elements of `sequence_of_sets`, removing all
    elements that are subsets of other elements.  Assumes that each
    element is a set or frozenset and that no element is repeated."""
    # The code below does not handle the case of a sequence containing
    # only the empty set, so let's just handle all easy cases now.
    if len(sequence_of_sets) <= 1:
        return list(sequence_of_sets)
    # We need an indexable sequence so that we can use a bitmap to
    # represent each set.
    if not isinstance(sequence_of_sets, collections.Sequence):
        sequence_of_sets = list(sequence_of_sets)
    # For each element, construct the list of all sets containing that
    # element.
    sets_containing_element = {}
    for i, s in enumerate(sequence_of_sets):
        for element in s:
            try:
                sets_containing_element[element] |= 1 << i
            except KeyError:
                sets_containing_element[element] = 1 << i
    # For each set, if the intersection of all of the lists in which it is
    # contained has length != 1, this set can be eliminated.
    out = [s for s in sequence_of_sets
           if s and is_power_of_two(reduce(
               operator.and_, (sets_containing_element[x] for x in s)))]
    return out

以上是 查找所有最大子集的高效算法 的全部内容， 来源链接： utcz.com/qa/426060.html

回到顶部