Determine si todos los elementos en una lista están presentes y en el mismo orden en otra lista

¿Cómo creo una función sublist() que toma dos listas, list1 y list2 , y devuelve True si list1 es una lista secundaria de list2 , y False caso contrario? list1 es una lista secundaria de list2 si los números en list1 aparecen en list2 en el mismo orden en que aparecen en list1 , pero no necesariamente de forma consecutiva. Por ejemplo,

 >>> sublist([1, 12, 3],[25, 1, 30, 12, 3, 40]) True >>> sublist([5, 90, 2],[90, 20, 5, 2, 17]) False 

Aquí hay una forma de hacerlo en tiempo lineal (y espacio constante) con un iterador:

 def sublist(a, b): seq = iter(b) try: for x in a: while next(seq) != x: pass else: return True except StopIteration: pass return False 

Básicamente, recorre cada elemento de la lista secundaria y ve si puede encontrar ese mismo elemento en la parte de la lista completa que aún no ha examinado. Si lo hace a través de toda la lista secundaria, significa que tenemos una coincidencia (de ahí la instrucción else en el bucle for). Si nos quedamos sin elementos para ver en la lista completa, significa que no tenemos una coincidencia.

Edición: He actualizado mi solución para que funcione con Python 3. Para Python 2.5 y seq.next() anteriores, el next(seq) debe reemplazarse con seq.next() .

Una solución muy ruda:

 def sublist(a, b): if not a: return True for k in range(len(b)): if a[0] == b[k]: return sublist(a[1:], b[k+1:]) return False print sublist([1, 12, 3], [25, 1, 30, 12, 3, 40]) # True print sublist([12, 1, 3], [25, 1, 30, 12, 3, 40]) # False 

Edición: actualización de velocidad

Aquí hay una solución iterativa que debería tener asintóticos óptimos:

 def sublist(x, y): if x and not y: return False i, lim = 0, len(y) for e in x: while e != y[i]: i += 1 if i == lim: return False i += 1 return True 

La solución de @sshashank124 tiene la misma complejidad, pero la dinámica será algo diferente: su versión atraviesa el segundo argumento varias veces, pero debido a que impulsa más trabajo en la capa C, probablemente sea mucho más rápida con una entrada más pequeña.

Edición : la solución de @hetman tiene esencialmente la misma lógica, pero es mucho más pythonica, aunque, contrariamente a mis expectativas, parece ser un poco más lenta. (También me equivoqué sobre el rendimiento de la solución de @ sshashan124; la sobrecarga de las llamadas recursivas parece ser mayor que el beneficio de hacer más trabajo en C.)

Aquí hay una versión simplificada:

 def sublist(a,b): try: return a[0] in b and sublist(a[1:],b[1+b.index(a[0]):]) except IndexError: return True >>> print sublist([1, 12, 3],[25, 1, 30, 12, 3, 40]) True >>> print sublist([5, 90, 2],[90, 20, 5, 2, 17]) False 

Felicitaciones por una pregunta engañosamente difícil. Creo que esto funcionará, pero no me sorprendería si me perdiera un caso de esquina, especialmente con elementos repetidos. Versión revisada inspirada en la solución recursiva de Hgu Nguyen :

 def sublist(a, b): index_a = 0 index_b = 0 len_a = len(a) len_b = len(b) while index_a < len_a and index_b < len_b: if a[index_a] == b[index_b]: index_a += 1 index_b += 1 else: index_b += 1 return index_a == len_a 

Algunos perfiles en bruto:

Dadas las listas que requieren atravesar la mayor parte o la totalidad de b , mi algoritmo sufre:

 a = [1, 3, 999999] b = list(range(1000000)) 

En mi PC, el algoritmo de Huu Nguyen o Hetman toma alrededor de 10 segundos para ejecutar 100 iteraciones del cheque. Mi algoritmo tarda 20 segundos.

Dado un éxito anterior, el algoritmo de Huu se queda muy atrás:

 a = [1, 3, 5] 

El algoritmo de Hetman o el mío pueden completar 100k cheques en menos de un segundo: Hetman's en 0.13 segundos en mi PC, el mío en 0.19 segundos. Huu tarda 16 segundos en completar 1k cheques. Estoy francamente sorprendido por ese grado de diferencia: la recursión puede ser lenta si no se optimiza el comstackdor, lo sé, pero 4 órdenes de magnitud es peor de lo que hubiera esperado.

Dada una lista de fallos a , el rendimiento se remonta a lo que vi cuando se requiere recorrer la segunda lista completa, comprensible, ya que no hay forma de saber que no habrá una secuencia al final que coincida con la lista que de otra manera no se puede comparar.

 a = [3, 1, 5] 

Nuevamente, unos 10 segundos para el algoritmo de Huu Nguyen o Hetman para 100 pruebas, 20 para la mía.

Las listas más largas ordenadas mantienen el patrón que vi para el éxito temprano. P.EJ:

 a = range(0, 1000, 20) 

Con el algoritmo de Hetman que tomó 10.99 segundos para completar 100k pruebas, mientras que el mío tomó 24.08. Huu tomó 28.88 para completar 100 pruebas.

Es cierto que estas no son la gama completa de pruebas que podría realizar, pero en todos los casos, el algoritmo de Hetman fue el que mejor funcionó.

¿Qué tal esto? Vamos a abordar esto desde el otro lado:

 def sublist(a,b): """returns True if a is contained in b and in the same order""" return a == [ch for ch in b if ch in a] 

Esto fallará en algunas circunstancias (por ejemplo, [1,2,3] debería ser un subconjunto de [1,1,8,2,3] ), pero es difícil decir exactamente cómo quiere que se implemente esto …

Para una solución rápida y sucia que funciona lentamente, pero será totalmente adecuada para arreglos del tamaño que mostró:

 def sublist(a,b): last = 0 for el_a in a: if el_a in b[last:]: last = b[last:].index(el_a) else: return False return True 

** Editado para trabajar con elementos no contiguos.

Aquí hay otra solución que puede ser más fácil de entender para los principiantes que Hetman . (Observe que está muy cerca de la implementación del OP en esta pregunta duplicada , pero evitando el problema de reiniciar la búsqueda desde el principio de b cada vez).

 def sublist(a, b): i = -1 try: for e in a: i = b.index(e, i+1) except ValueError: return False else: return True 

Por supuesto, esto requiere que b sea ​​una list , mientras que la respuesta de Hetman permite cualquier iteración. Y creo que (para la gente que entiende Python lo suficientemente bien) también es menos simple que la respuesta de Hetman.

Algorítmicamente, está haciendo lo mismo que la respuesta de Hetman, por lo que es O (N) tiempo y O (1) espacio. Pero en la práctica, puede ser más rápido, al menos en CPython, ya que estamos moviendo el bucle interno de un Python while estamos alrededor de un iterador a un bucle de obtención rápida de C (dentro de list.index ). Nuevamente, puede ser más lento, porque estamos copiando alrededor de ese valor i lugar de tener todo el estado incrustado dentro de un iterador (implementado por C). Si es importante, pruébalos con tus datos reales. 🙂

Aquí hay una mejor solución usando regex :

 import re def exiSt(short,long): r = ''.join(["(.*"+str[x]+")" for x in short]) return re.match(r,','.join([str(x) for x in long])) == None long = [1, 2, 3, 4, 5] short1 = [1,2,5] short2 = [1,5,3] exiSt(short1,long) >> True exiSt(short2,long) >> False 
 def sublist(a, b): "if set_a is not subset of set_b then obvious answer is False" if not set(a).issubset(set(b)): return False n = 0 for i in a: if i in b[n:]: "+1 is needed to skip consecutive duplicates, ie sublist([2,1,1],[2,1]) = False" "if +1 is absent then sublist([2,1,1],[2,1]) = True" "choose to use or not to use +1 according to your needs" n += b[n:].index(i) + 1 else: return False return True