Фильтрация списка целых чисел в диапазоне, чтобы исключить подмножества в python

Question

Я пытаюсь найти более быстрый способ фильтрации моего списка диапазонов, так что любой диапазон, который может быть полностью покрыт большим диапазоном, будет исключен. Например,

#all ranges have width >1, which means no such case like xx=[1,1] in my list 
#each range itself is sorted. E.g. no such case like [1,3,2]. It is already like [1,2,3] 
#each range only contains continuous integers. E.g. no such case like [3,5,7], it will only be like [3,4,5,6,7]. In fact, you could simply consider the first and last integer of the range to know the whole range. 
aa=[1,2,3] 
bb=[2,3,4] 
cc=[1,2] 
dd=[0,1,2] 

RangeList=[aa,bb,cc,dd] 

#FinalList=[aa,bb,dd] 

куб.см могут быть покрыты или аа дд (я считаю это как подмножество), поэтому хотелось бы, чтобы исключить его. Я определенно мог бы написать цикл для n^2 сравнений, но я был бы признателен за более быстрый метод, так как у меня много таких диапазонов.

Answer 1

Вы можете решить эту проблему путем сортировки первых:

import operator 
ranges=[[0,1,2,3,4], [1,2], [0,1], [2,3,4], [3,4,5], [3,4,5,6], [4,5], [6,7], [5,6]] 
sorted_ranges = sorted(ranges,key=operator.itemgetter(-1),reverse=True) 
sorted_ranges = sorted(sorted_ranges,key=operator.itemgetter(0)) 

filtered = [] 
i,j = 0,0  

while i < len(sorted_ranges): 
    filtered.append(sorted_ranges[i]) 
    j = i+1 
    while j < len(sorted_ranges) and sorted_ranges[i][-1] >= sorted_ranges[j][-1]: 
     print "Remove " , sorted_ranges.pop(j) , "dominated by",sorted_ranges[i] 
    i+=1 

print "RESULT",filtered 

Вам нужно будет сортировать по первому элементу в порядке возрастания и убывания для последнего элемента. я использовал два явных вызовов сортируются, но вы можете определить свою функцию КССА, чтобы сделать это за один проход:

sorted_ranges = sorted(ranges,cmp=lambda x,y: (x[0]-y[0]) if ((x[0]-y[0]) != 0) else (y[-1]-x[-1])) 

Таким образом, диапазоны доминирующих появятся первыми. Обратите внимание, что вложенный цикл while после сортировки имеет сложность O (n), поскольку каждый элемент проверяется только один раз и либо удален, либо добавлен в окончательный набор. Сложность всего алгоритма представляет собой О (NlogN)

Answer 2

Используя sets, issubset(), filter():

ranges = [[0,1,2,3,4], [1,2], [0,1], [2,3,4], [3,4,5], [3,4,5,6], [4,5], [6,7], [5,6]] 

# Use 'frozenset' as it is hashable to put in a big 'set' 
sets = set([frozenset(a) for a in ranges]) 

def f(x): 
    for y in sets: 
     if x == y: 
      continue 
     if x.issubset(y): 
      return False 
    return True 

result = [list(a) for a in filter(f, sets)] 
print 'Result=', result 

f функция отфильтровывает любой набор найденный на входе.

Result= [[3, 4, 5, 6], [0, 1, 2, 3, 4], [6, 7]] 

Не пропустите тесты производительности.

Answer 3

Моя первая мысль была:

compressed = dict() 
for lst in sorted(RangeList,reverse=True, key= lambda x: (x[0],x[1])): 
    key = lst[0] 
    if key not in compressed: 
     compressed[key] = lst 
print compressed.values() 

Но IGON отметил, что скучает внутренние подмножества. Я думаю, что следующий будет исправить:

RangeList = sorted(RangeList,reverse=True, key= lambda x: (-x[0],x[-1])) 
lst = RangeList[0] 
oldstart = lst[0] 
oldend = lst[-1] 
compressed = {oldstart: lst} 
for lst in RangeList[1:]: 
    start = lst[0] 
    end = lst[-1] 
    if (start not in compressed and oldend < end): 
     compressed[start] = lst 
     oldstart, oldend = start, end 

print compressed.values() 

Answer 4

Это использует set и issubset, но первый сортирует список по размеру, а функция filter снова проходит вход в обратном порядке, пытаясь оптимизировать поиск. Это может улучшить порядок O().

ranges = [[0,1,2,3,4], [1,2], [0,1], [2,3,4], [3,4,5], [3,4,5,6], [4,5], [6,7], [5,6]] 

sets = [set(a) for a in ranges] 
sets.sort(key=len) 
reverse_sets = sets[:] 
reverse_sets.reverse() 

def f(x): 
    for y in reverse_sets: 
     if x == y: 
      continue 
     if x.issubset(y): 
      return False 
    return True 

print 'Result=', [list(a) for a in filter(f, sets)] 

Результат:

Result= [[6, 7], [3, 4, 5, 6], [0, 1, 2, 3, 4]]