Фильтрация списка Python: удаление подмножеств из списка списков

Это может быть упрощено, но:

 l = [[1, 2, 4, 8], [1, 2, 4, 5, 6], [1, 2, 3], [2, 3, 21], [1, 2, 3, 4], [1, 2, 3, 4, 5, 6, 7]] l2 = l[:] for m in l: for n in l: if set(m).issubset(set(n)) and m != n: l2.remove(m) break print l2 [[1, 2, 4, 8], [2, 3, 21], [1, 2, 3, 4, 5, 6, 7]] 

Этот код должен быть довольно эффективным с точки зрения памяти. Помимо сохранения начального списка списков, этот код использует незначительную дополнительную память (временные наборы или копии списков не создаются).

 def is_subset(needle,haystack): """ Check if needle is ordered subset of haystack in O(n) """ if len(haystack) < len(needle): return False index = 0 for element in needle: try: index = haystack.index(element, index) + 1 except ValueError: return False else: return True def filter_subsets(lists): """ Given list of lists, return new list of lists without subsets """ for needle in lists: if not any(is_subset(needle, haystack) for haystack in lists if needle is not haystack): yield needle my_lists = [[1, 2, 4, 8], [1, 2, 4, 5, 6], [1, 2, 3], [2, 3, 21], [1, 2, 3, 4], [1, 2, 3, 4, 5, 6, 7]] print list(filter_subsets(my_lists)) >>> [[1, 2, 4, 8], [2, 3, 21], [1, 2, 3, 4, 5, 6, 7]] 

И, просто для удовольствия, однострочный:

 def filter_list(L): return [x for x in L if not any(set(x)<=set(y) for y in L if x is not y)] 

Список является суперлистом, если он не является подмножеством какого-либо другого списка. Это подмножество другого списка, если каждый элемент списка можно найти по порядку в другом списке.

Вот мой код:

 def is_sublist_of_any_list(cand, lists): # Compare candidate to a single list def is_sublist_of_list(cand, target): try: i = 0 for c in cand: i = 1 + target.index(c, i) return True except ValueError: return False # See if candidate matches any other list return any(is_sublist_of_list(cand, target) for target in lists if len(cand) <= len(target)) # Compare candidates to all other lists def super_lists(lists): return [cand for i, cand in enumerate(lists) if not is_sublist_of_any_list(cand, lists[:i] + lists[i+1:])] if __name__ == '__main__': lists = [[1, 2, 4, 8], [1, 2, 4, 5, 6], [1, 2, 3], [2, 3, 21], [1, 2, 3, 4], [1, 2, 3, 4, 5, 6, 7]] superlists = super_lists(lists) print superlists 

Вот результаты:

 [[1, 2, 4, 8], [2, 3, 21], [1, 2, 3, 4, 5, 6, 7]] 

Изменить: результаты для вашего более позднего набора данных.

 >>> lists = [[2, 16, 17], [1, 2, 3, 4, 5, 6, 7], [1], [1, 2, 3, 4], [1, 2], [17, 18, 19, 22, 41, 48], [2, 3], [1, 2, 3], [50, 69], [1, 2, 3], [2, 3, 21], [1, 2, 3], [1, 2, 4, 8], [1, 2, 4, 5, 6]] >>> superlists = super_lists(lists) >>> expected = [[2, 16, 17], [1, 2, 3, 4, 5, 6, 7], [17, 18, 19, 22, 41, 48], [5 0, 69], [2, 3, 21], [1, 2, 4, 8]] >>> assert(superlists == expected) >>> print superlists [[2, 16, 17], [1, 2, 3, 4, 5, 6, 7], [17, 18, 19, 22, 41, 48], [50, 69], [2, 3, 21], [1, 2, 4, 8]] 

Это похоже на работу:

 original=[[1, 2, 4, 8], [1, 2, 4, 5, 6], [1, 2, 3], [2, 3, 21], [1, 2, 3, 4], [1, 2, 3, 4, 5, 6, 7]] target=[[1, 2, 4, 8], [2, 3, 21], [1, 2, 3, 4, 5, 6, 7]] class SetAndList: def __init__(self,aList): self.list=aList self.set=set(aList) self.isUnique=True def compare(self,aList): s=set(aList) if self.set.issubset(s): #print self.list,'superceded by',aList self.isUnique=False def listReduce(lists): temp=[] for l in lists: for t in temp: t.compare(l) temp.append( SetAndList(l) ) return [t.list for t in temp if t.isUnique] print listReduce(original) print target 

Это отображает вычисленный список и цель для визуального сравнения.

Раскомментируйте строку печати в методе сравнения, чтобы увидеть, как все списки списываются.

Протестировано с помощью python 2.6.2

Я реализовал другой issubseq потому что ваш не говорит, что [1, 2, 4, 5, 6] является подпоследовательностью [1, 2, 3, 4, 5, 6, 7] , например (кроме того, ). Решение, которое я придумал, выглядит так:

  def is_subseq(a, b): if len(a) > len(b): return False start = 0 for el in a: while start < len(b): if el == b[start]: break start = start + 1 else: return False return True def filter_partial_matches(sets): return [s for s in sets if all([not(is_subseq(s, ss)) for ss in sets if s != ss])] 

Простой тестовый пример, учитывая ваши входы и выходы:

 >>> test = [[1, 2, 4, 8], [1, 2, 4, 5, 6], [1, 2, 3], [2, 3, 21], [1, 2, 3, 4], [1, 2, 3, 4, 5, 6, 7]] >>> another_test = [[1, 2, 3, 4], [2, 4, 3], [3, 4, 5]] >>> filter_partial_matches(test) [[1, 2, 4, 8], [2, 3, 21], [1, 2, 3, 4, 5, 6, 7]] >>> filter_partial_matches(another_test) [[1, 2, 3, 4], [2, 4, 3], [3, 4, 5]] 

Надеюсь, поможет!

 list0=[[1, 2, 4, 8], [1, 2, 4, 5, 6], [1, 2, 3], [2, 3, 21], [1, 2, 3, 4], [1, 2, 3, 4, 5, 6, 7]] for list1 in list0[:]: for list2 in list0: if list2!=list1: len1=len(list1) c=0 for n in list2: if n==list1[c]: c+=1 if c==len1: list0.remove(list1) break 

Это фильтрует list0 на месте, используя его копию. Это хорошо, если ожидается, что результат будет примерно того же размера, что и оригинал, для удаления будет только несколько «подмножеств».

Если ожидается, что результат будет небольшим, а оригинал будет большим, вы можете предпочесть этот, у кого больше памяти, поскольку он не копирует исходный список.

 list0=[[1, 2, 4, 8], [1, 2, 4, 5, 6], [1, 2, 3], [2, 3, 21], [1, 2, 3, 4], [1, 2, 3, 4, 5, 6, 7]] result=[] for list1 in list0: subset=False for list2 in list0: if list2!=list1: len1=len(list1) c=0 for n in list2: if n==list1[c]: c+=1 if c==len1: subset=True break if subset: break if not subset: result.append(list1) 

Изменить: мне действительно нужно улучшить понимание прочитанного. Вот ответ на то, что было на самом деле спрошено. Он использует тот факт, что « A is super of B » означает « len(A) > len(B) or A == B ».

 def advance_to(it, value): """Advances an iterator until it matches the given value. Returns False if not found.""" for item in it: if item == value: return True return False def has_supersequence(seq, super_sequences): """Checks if the given sequence has a supersequence in the list of supersequences.""" candidates = map(iter, super_sequences) for next_item in seq: candidates = [seq for seq in candidates if advance_to(seq, next_item)] return len(candidates) > 0 def find_supersequences(sequences): """Finds the supersequences in the given list of sequences. Sequence A is a supersequence of sequence B if B can be created by removing items from A.""" super_seqs = [] for candidate in sorted(sequences, key=len, reverse=True): if not has_supersequence(candidate, super_seqs): super_seqs.append(candidate) return super_seqs print(find_supersequences([[1, 2, 4, 8], [1, 2, 4, 5, 6], [1, 2, 3], [2, 3, 21], [1, 2, 3, 4], [1, 2, 3, 4, 5, 6, 7]])) #Output: [[1, 2, 3, 4, 5, 6, 7], [1, 2, 4, 8], [2, 3, 21]] 

Если вам нужно также сохранить исходный порядок последовательностей, find_supersequences() должна отслеживать позиции последовательностей и сортировать результат после этого.

Уточненный ответ после нового теста:

 original= [[2, 16, 17], [1, 2, 3, 4, 5, 6, 7], [1], [1, 2, 3, 4], [1, 2], [17, 18, 19, 22, 41, 48], [2, 3], [1, 2, 3], [50, 69], [1, 2, 3], [2, 3, 21], [1, 2, 3], [1, 2, 4, 8], [1, 2, 4, 5, 6]] class SetAndList: def __init__(self,aList): self.list=aList self.set=set(aList) self.isUnique=True def compare(self,other): if self.set.issubset(other.set): #print self.list,'superceded by',other.list self.isUnique=False def listReduce(lists): temp=[] for l in lists: s=SetAndList(l) for t in temp: t.compare(s) s.compare(t) temp.append( s ) temp=[t for t in temp if t.isUnique] return [t.list for t in temp if t.isUnique] print listReduce(original) 

Вы не дали требуемый результат, но я предполагаю, что это правильно, поскольку [1,2,3] не отображается в выводе.

Спасибо всем, кто предложил решения и справился с моими иногда ошибочными наборами данных. Используя решение @hughdbrown, я изменил его на то, что хотел:

Модификация заключалась в том, чтобы использовать скользящее окно над целью, чтобы гарантировать, что последовательность подмножества найдена. Думаю, я должен был использовать более подходящее слово, чем «Установить», чтобы описать мою проблему.

 def is_sublist_of_any_list(cand, lists): # Compare candidate to a single list def is_sublist_of_list(cand, target): try: i = 0 try: start = target.index(cand[0]) except: return False while start < (len(target) + len(cand)) - start: if cand == target[start:len(cand)]: return True else: start = target.index(cand[0], start + 1) except ValueError: return False # See if candidate matches any other list return any(is_sublist_of_list(cand, target) for target in lists if len(cand) <= len(target)) # Compare candidates to all other lists def super_lists(lists): a = [cand for i, cand in enumerate(lists) if not is_sublist_of_any_list(cand, lists[:i] + lists[i+1:])] return a lists = [[2, 16, 17], [1, 2, 3, 4, 5, 6, 7], [1], [1, 2, 3, 4], [1, 2], [17, 18, 19, 22, 41, 48], [2, 3], [1, 2, 3], [50, 69], [1, 2, 3], [2, 3, 21], [1, 2, 3], [1, 2, 4, 8], [1, 2, 4, 5, 6]] expect = [[2, 16, 17], [1, 2, 3, 4, 5, 6, 7], [17, 18, 19, 22, 41, 48], [50, 69], [2, 3, 21], [1, 2, 4, 8], [1, 2, 4, 5, 6]] def test(): out = super_lists(list(lists)) print "In : ", lists print "Out : ", out assert (out == expect) 

Результат:

 In : [[2, 16, 17], [1, 2, 3, 4, 5, 6, 7], [1], [1, 2, 3, 4], [1, 2], [17, 18, 19, 22, 41, 48], [2, 3], [1, 2, 3], [50, 69], [1, 2, 3], [2, 3, 21], [1, 2, 3], [1, 2, 4, 8], [1, 2, 4, 5, 6]] Out : [[2, 16, 17], [1, 2, 3, 4, 5, 6, 7], [17, 18, 19, 22, 41, 48], [50, 69], [2, 3, 21], [1, 2, 4, 8], [1, 2, 4, 5, 6]] 

Так что вы действительно хотели знать, был ли список подстрокой, так сказать, другой, со всеми соответствующими элементами подряд. Вот код, который преобразует кандидат и целевой список в строки, разделенные запятыми, и делает сравнение подстроки, чтобы увидеть, появляется ли кандидат в целевом списке

 def is_sublist_of_any_list(cand, lists): def comma_list(l): return "," + ",".join(str(x) for x in l) + "," cand = comma_list(cand) return any(cand in comma_list(target) for target in lists if len(cand) <= len(target)) def super_lists(lists): return [cand for i, cand in enumerate(lists) if not is_sublist_of_any_list(cand, lists[:i] + lists[i+1:])] 

Функция comma_list () помещает в список ведущие и конечные запятые, чтобы гарантировать, что целые числа будут полностью разделены. В противном случае, например, [1] будет подмножеством [100].