Encuentra todos los sublistas posibles de una lista

Digamos que tengo la siguiente lista

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

Quiero encontrar todas las sublistas posibles de cierta longitud donde no contengan un número determinado y sin perder el orden de los números.

Por ejemplo, todas las sublistas posibles con longitud 6 sin 12 son:

 [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] 

El problema es que quiero hacerlo en una lista muy grande y quiero la forma más rápida.

Actualizar con mi método:

 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) 

Sé que no es el mejor método, por eso necesito uno mejor.

Una solución directa, no optimizada sería

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

Una versión optimizada:

 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 

Utilice 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))] 

Huellas dactilares:

 [(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)] 

La forma más sencilla en que puedo pensar sería eliminar el número excluido de la lista y luego usar itertools.combinations() para generar las sublistas deseadas. Esto tiene la ventaja adicional de que producirá las sublistas de forma iterativa.

 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 

Salida:

 [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] 

Me gusta construir soluciones a partir de pequeñas piezas compostables. Unos años de escribir Haskell te hace eso. Así que lo haría así …

Primero, esto devolverá un iterador sobre todas las listas secundarias, en orden ascendente de longitud, comenzando con la lista vacía:

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

En general, se nos desaconseja el uso de nombres de variables de una sola letra, pero creo que, en pocas palabras, un código altamente abstracto es algo perfectamente razonable.

(Por cierto, para omitir la lista vacía, use el range(1, len(l) + 1) lugar.)

Entonces podemos resolver su problema en general agregando sus criterios:

 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 ) 

Así por ejemplo:

 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) 

Tengo una respuesta pero creo que no es la mejor:

 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 

Obtendrá el resultado, pero debido a que tendrá muchas listas secundarias, necesitará mucha memoria y mucho tiempo. Creo que no es una buena manera.

Mi bash de crear recursivamente todas las listas de listas posibles. El parámetro de profundidad solo toma el número de elementos para eliminar de cada lista. Esto no es una ventana deslizante.

Código:

 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 

Ejemplos (escritos de forma interactiva en 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] ]

Algunos casos de borde:

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)

[]

NOTA: la lista de salida de listas incluye duplicados.