Отбирать список для поиска самых непересекающихся членов в Python

Question

Каждый элемент в списке L является кортежем формы (поля, размер). Например

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) со стороной -эффект обновления списка замеченных элементов.)

Это должно быть O (n log n) из-за sort вместо вашего O (n^2).