list - 剔除列表以在 Python 中找到最大的非相交成员

Question

列表 L 中的每个元素都是一个形式为 (fields, size) 的元组。例如

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

我想剔除该列表，使其仅包含不相交的成员，并且剩余的每个成员都大于它可能相交的任何其他成员。所以示例列表 L 将简化为

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)]

有没有更好/更快/更 Pythonic 的方式来做到这一点？

谢谢您的帮助！

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)，其副作用是更新可见成员列表。）

由于sort, 而不是 O(n^2)，这应该是 O(n log n)。