Найти все возможные подсписки из списка

Question

Допустим, у меня есть следующий список

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18] 

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

Например, все возможные подсписки с длиной 6 без 12:

[1,2,3,4,5,6] 
[2,3,4,5,6,7] 
[3,4,5,6,7,8] 
[4,5,6,7,8,9] 
[5,6,7,8,9,10] 
[6,7,8,9,10,11] 
[13,14,15,16,17,18] 

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

Обновление с моим методом:

oldlist = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18] 
newlist = [] 
length = 6 
exclude = 12 
for i in oldlist: 
    if length+i>len(oldlist): 
     break 
    else: 
     mylist.append(oldlist[i:(i+length)] 
for i in newlist: 
    if exclude in i: 
     newlist.remove(i) 

Я знаю, что это не самый лучший способ, поэтому мне нужно лучше.

Answer 1

Прямолинейный, не оптимальным решением было бы

result = [sublist for sublist in 
     (lst[x:x+size] for x in range(len(lst) - size + 1)) 
     if item not in sublist 
    ] 

оптимизированная версия:

result = [] 
start = 0 
while start < len(lst): 
    try: 
     end = lst.index(item, start + 1) 
    except ValueError: 
     end = len(lst) 
    result.extend(lst[x+start:x+start+size] for x in range(end - start - size + 1)) 
    start = end + 1 

Answer 2

Использование itertools.combinations:

import itertools 
mylist = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18] 
def contains_sublist(lst, sublst): 
    n = len(sublst) 
    return any((sublst == lst[i:i+n]) for i in xrange(len(lst)-n+1)) 
print [i for i in itertools.combinations(mylist,6) if 12 not in i and contains_sublist(mylist, list(i))] 

Печать:

[(1, 2, 3, 4, 5, 6), (2, 3, 4, 5, 6, 7), (3, 4, 5, 6, 7, 8), (4, 5, 6, 7, 8, 9), (5, 6, 7, 8, 9, 10), (6, 7, 8, 9, 10, 11), (13, 14, 15, 16, 17, 18)] 

Answer 3

Простейший способ, я могу думать, состоит в том, чтобы удалить исключенное число из списка, а затем использовать itertools.combinations() для генерации желаемых подсписок. Это имеет дополнительное преимущество в том, что он будет производить подсписки итеративно.

from itertools import combinations 

def combos_with_exclusion(lst, exclude, length): 
    for combo in combinations((e for e in lst if e != exclude), length): 
     yield list(combo) 

mylist = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18] 

for sublist in combos_with_exclusion(mylist, 12, 6): 
    print sublist 

Выход:

[1, 2, 3, 4, 5, 6] 
[1, 2, 3, 4, 5, 7] 
[1, 2, 3, 4, 5, 8] 
[1, 2, 3, 4, 5, 9] 
[1, 2, 3, 4, 5, 10] 
[1, 2, 3, 4, 5, 11] 
[1, 2, 3, 4, 5, 13] 
     ... 
[11, 14, 15, 16, 17, 18] 
[13, 14, 15, 16, 17, 18] 

Answer 4

Моя попытка рекурсивно создавать все возможные список списков. Параметр depth просто берет количество элементов для удаления из каждого списка. Это не скользящее окно.

Код:

def sublists(input, depth): output= [] if depth > 0: for i in range(0, len(input)): sub= input[0:i] + input[i+1:] output += [sub] output.extend(sublists(sub, depth-1)) return output

Примеры (набранные в интерактивном режиме в Python3):

sublists([1,2,3,4],1)

[[2, 3, 4], [1, 3, 4], [1, 2, 4], [1, 2, 3]]

sublists([1,2,3,4],2)

[[2, 3, 4], [3, 4], [2, 4], [2, 3], [1, 3, 4], [3, 4], [1, 4], [1, 3], [1, 2, 4], [2, 4], [1, 4 ], [1, 2], [1, 2, 3], [2, 3], [1, 3], [1, 2]]

sublists([1,2,3,4],3)

[[2, 3, 4 ], [3, 4], [4], [3], [2, 4], [4], [2], [2, 3], [3], [2], [1, 3, 4 ], [3, 4], [4], [3], [1, 4], [4], [1], [1, 3], [3], [1], [1, 2, 4 ], [2, 4], [4], [2], [1, 4], [4], [1], [1, 2], [2], [1], [1, 2, 3 ], [2, 3], [3], [2], [1, 3], [3], [1], [1, 2], [2], [1]]

Некоторые края случаев:

sublists([1,2,3,4],100)

[[2, 3, 4], [3, 4], [4], [3], [2, 4], [4], [2], [2, 3], [3], [ 2], [1, 3, 4], [3, 4], [4], [3], [1, 4], [4], [1], [1, 3], [3], [ 1], [1, 2, 4], [2, 4], [4], [2], [1, 4], [4], [1], [1, 2], [2], [ 1], [1, 2, 3], [2, 3], [3], [2], [1, 3], [3], [1], [1, 2], [2], [ 1]]

sublists([], 1)

[]

Примечание: список вывода списков включает дубликаты.

Answer 5

У меня есть ответ, но я думаю, что это не самое лучшее:

oldlist = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18] 
result = [] 
def sub_list(lst): 
    if len(lst) <= 1: 
     result.append(tuple(lst)) 
     return 
    else: 
     result.append(tuple(lst)) 
    for i in lst: 
     new_lst = lst[:] 
     new_lst.remove(i) 
     sub_list(new_lst) 
sub_list(oldlist) 
newlist = set(result) # because it have very very very many the same 
         # sublist so we need use set to remove these also 
         # use tuple above is also the reason 
print newlist 

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

Answer 6

Мне нравится создавать решения из небольших составных частей. Несколько лет написания Haskell делает это с вами. Так что я хотел бы сделать это, как это ...

Во-первых, это вернет итератор по всем подсписки в порядке возрастания длины, начиная с пустого списка:

from itertools import chain, combinations 

def all_sublists(l): 
    return chain(*(combinations(l, i) for i in range(len(l) + 1))) 

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

(BTW, чтобы опустить пустой список, используйте range(1, len(l) + 1) вместо этого.)

Тогда мы можем решить вашу проблему в целом, добавляя свои критерии:

def filtered_sublists(input_list, length, exclude): 
    return (
     l for l in all_sublists(input_list) 
     if len(l) == length and exclude not in l 
    ) 

Так, например:

oldlist = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18] 
length = 6 
exclude = 12 
newlist = filtered_sublists(old_list, length, exclude)