Verifique la presencia de una lista dividida en Python
Quiero escribir una función que determine si existe una sublista en una lista más grande.
list1 = [1,0,1,1,1,0,0]
list2 = [1,0,1,0,1,0,1]
#Should return true
sublistExists(list1, [1,1,1])
#Should return false
sublistExists(list2, [1,1,1])
¿Existe una función de Python que pueda hacer esto?
Pongámonos un poco funcionales, ¿vale? :)
def contains_sublist(lst, sublst):
n = len(sublst)
return any((sublst == lst[i:i+n]) for i in range(len(lst)-n+1))
Tenga en cuenta que any()se detendrá en la primera coincidencia de sublst dentro de lst, o fallará si no hay coincidencia, después de las operaciones O(m*n)
Si está seguro de que sus entradas solo contendrán los dígitos 0 y 1, puede convertir a cadenas:
def sublistExists(list1, list2):
return ''.join(map(str, list2)) in ''.join(map(str, list1))
Esto crea dos cadenas, por lo que no es la solución más eficiente, pero dado que aprovecha el algoritmo de búsqueda de cadenas optimizado en Python, probablemente sea suficiente para la mayoría de los propósitos.
Si la eficiencia es muy importante, puedes consultar el algoritmo de búsqueda de cadenas de Boyer-Moore , adaptado para trabajar en listas.
Una búsqueda ingenua tiene el peor de los casos O(n*m), pero puede ser adecuada si no puede utilizar el truco de conversión a cadena y no necesita preocuparse por el rendimiento.
Ninguna función que yo sepa
def sublistExists(list, sublist):
for i in range(len(list)-len(sublist)+1):
if sublist == list[i:i+len(sublist)]:
return True #return position (i) if you wish
return False #or -1
Como señaló Mark, esta no es la búsqueda más eficiente (es O(n*m)). Este problema se puede abordar de forma muy parecida a la búsqueda de cadenas.
