在Python中查找最大不相交成员的剔除列表

Question

列表L中的每个元素都是该形式的元组（字段、大小）。例如

L = [ (['A','B'], 5), (['A'], 6), ('C', 1)]

我想挑选名单，使它只包含非相交的成员，每个成员仍然是大于任何其他成员，它可能已经相交。所以我的例子列表会简化为

L = [ (['A'], 6), ('C', 1)]

目前我已经实现了如下：

def betterItem(x, y):
    return (x != y and
            set(x[0]) & set(y[0]) and
            x[1] > y[1])

for i in range(len(L)-1):
    L[:] = [x for x in L for y in L if betterItem(x, y)]

有没有更好的/更快的/更像Python的方法？你知道吗

谢谢你的帮助！你知道吗

Answer 1

L = [(['A','B'], 5), (['A'], 6), (['C'], 1)]

# sort by descending value
L.sort(key=lambda s:s[1], reverse=True)

# keep track of what members have already occurred
seen = set()

# Cull L - ignore members already in `seen`
# (Because it is presorted, already-seen members must have had a higher value)
L = [seen.update(i) or (i,j) for i,j in L if seen.isdisjoint(i)]

结果

[(['A'], 6), (['C'], 1)]

（这个列表理解使用了一点技巧：seen.update总是返回None，而None or x总是返回x-所以seen.update(i) or (i,j)返回元组(i,j)，其副作用是更新seen成员列表。）

由于sort，这应该是O（n logn），而不是O（n^2）。你知道吗