我有一组独特的集合(表示为位掩码),并希望消除作为另一个元素的正确子集的所有元素.例如:
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在恒定时间内运行.
Gen*_*ene 15
假设您标记了所有输入集.
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 是(tick'表示集补集)的子集的A超集.BA'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) )'
再次,tick'设置为补码.联合表单的计算速度可能会快一些.Y包含已被取代的最大集合S.必须从最大集合中删除它们I.最后添加S为最大集并I使用S'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
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