Сначала создайте новый список, который сохраняет исходные оценки, но преобразует наборы слов в наборы для более быстрого сравнения и проверки набора членов.
Перечисляет каждый набор слов и оценок в этом новом списке и сравнивает против всех оставшихся сетов и очков. Используя наборы, мы можем обнаружить подмножества через s1.issubset(s2), а суперсеты через s1.issuperset(s2).
После обнаружения подмножества / надмножества мы сравниваем оценки. Если текущая запись имеет более высокий балл, мы помечаем другую для удаления, а затем продолжаем сравнивать с остальными записями. В противном случае мы добавляем текущее местоположение индекса к набору индексов для последующего удаления и продолжаем все оставшиеся сравнения с этой записью.
После того, как мы обработали все записи, мы используем условное понимание списка для создания новый список всех записей, которые нужно сохранить.
С точки зрения сравнений подмножеств, сложность времени наихудшего случая равна O (n ^ 2) / 2, которая по-прежнему равна O (n ^ 2). Конечно, каждое сравнение подмножеств имеет свою собственную временную сложность, основанную на количестве уникальных слов в каждом подсписке. Таким образом, это решение выполняет то же количество сравнений, что и метод OP for x,y in combinations(mylist,2), но сравнения подмножеств / надмножеств выполняются с использованием наборов, а не списков. В результате этот метод все еще должен быть значительно быстрее.
def process_list(my_list):
# Convert tuples to sets.
my_sets = [(set(tuples), score) for tuples, score in my_list]
idx_to_remove = set()
for i, (subset1, score1) in enumerate(my_sets):
for j, (subset2, score2) in enumerate(my_sets[(i + 1):], start=i + 1):
if subset1.issubset(subset2) | subset1.issuperset(subset2):
# Subset/Superset detected.
idx_to_remove.add(i if score1 < score2 else j)
# Remove filtered items from list and return filtered list.
return [tup for n, tup in enumerate(my_list) if n not in idx_to_remove]
# TEST CASES
# Case 1.
mylist = [
[('only','one','time'), 10.54],
[('one','time'), 3.21],
[('red','hot','chili','peppers'), 0.223],
[('red','hot','chili'), 1.98],
]
>>> process_list(mylist)
[[('only', 'one', 'time'), 10.54], [('red', 'hot', 'chili'), 1.98]]
# Case 2.
# ('a', 'b', 'd') is superset of ('a', 'b') and has a lower score, so remove former.
# ('a', 'b') is a subset of ('a', 'b', 'c') and has a lower score, so remove former.
mylist = [[('a', 'b', 'c'), 3], [('a', 'b', 'd'), 1], [('a', 'b'), 2]]
>>> process_list(mylist)
[[('a', 'b', 'c'), 3]]
# Case 3. Same items as Case 2, but different order. Same logic as Case 2.
mylist = [[('a', 'b'), 2], [('a', 'b', 'c'), 3], [('a', 'b', 'd'), 1]]
>>> process_list(mylist)
[[('a', 'b', 'c'), 3]]
# Case 4.
# ('a', 'b', 'c') is a superset of ('a', 'b') and has a lower score, so remove former.
# ('d','c') is a subset of ('d','c','w') and has a lower score, so remove former.
mylist = [[('a', 'b'), 2], [('a', 'b', 'c'), 1], [('d','c','w'), 4], [('d','c'), 2]]
>>> process_list(mylist)
[[('a', 'b'), 2], [('d', 'c', 'w'), 4]]