Verifique la presencia de una lista dividida en Python

Question

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

¿Hay una función de Python que puede hacer esto?

Answer 1

Si está seguro de que sus entradas contendrán solamente un solo dígito 0 y 1, entonces se puede convertir en 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 ya que se necesita La ventaja del algoritmo optimizado de búsqueda de cadenas en Python es probablemente lo suficientemente bueno para la mayoría de los propósitos.

Si la eficiencia es muy importante, puede mirar el algoritmo de búsqueda de cadenas Boyer-Moore, adaptado para trabajar en las listas.

Una búsqueda ingenua tiene O (n * m) en el peor de los casos pero puede ser adecuada si no puede usar la conversión al truco de cuerdas y no tiene que preocuparse por el rendimiento.

Answer 2

Sin 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 señaló Marcos, esto no es la búsqueda más eficiente (que es O (n * m)). Este problema se puede abordar de forma muy similar a la búsqueda de cadenas.

Answer 3

Funcionemos un poco, ¿o sí? :)

def contains_sublist(lst, sublst): 
    n = len(sublst) 
    return any((sublst == lst[i:i+n]) for i in xrange(len(lst)-n+1)) 

Tenga en cuenta que any() se detendrá en el primer partido de sublst dentro LST - o fallar si no hay ninguna coincidencia, después de O (m * n) operaciones

Answer 4

Aquí está una manera que funcione para listas simples que es un poco menos frágil que

def sublistExists(haystack, needle): 
    def munge(s): 
     return ", "+format(str(s)[1:-1])+"," 
    return munge(needle) in munge(haystack) 

Answer 5

si iam comprensión de Mark esto correctamente, tienen una lista más grande, como:

list_A= ['john', 'jeff', 'dave', 'shane', 'tim'] 

Luego hay otras listas

list_B= ['sean', 'bill', 'james'] 

list_C= ['cole', 'wayne', 'jake', 'moose'] 

y entonces añadir el listas B y C a una lista

list_A.append(list_B) 

list_A.append(list_C) 

así que cuando i imprimir list_A

print (list_A) 

i obtener la siguiente salida

['john', 'jeff', 'dave', 'shane', 'tim', ['sean', 'bill', 'james'], ['cole', 'wayne', 'jake', 'moose']] 

ahora que quiero comprobar si existe la sublista:

for value in list_A: 
    value= type(value) 
    value= str(value).strip('<>').split()[1] 
    if (value == "'list'"): 
     print "True" 
    else: 
     print "False" 

Esto le dará 'True' si tiene alguna lista secundaria dentro de la lista más grande.

Answer 6

Basta con crear conjuntos de las dos listas y utilizar la función issubset:

def sublistExists(big_list, small_list): 
    return set(small_list).issubset(set(big_list)) 

Answer 7

def sublistExists(x, y): 
    occ = [i for i, a in enumerate(x) if a == y[0]] 
    for b in occ: 
     if x[b:b+len(y)] == y: 
      print 'YES-- SUBLIST at : ', b 
      return True 
     if len(occ)-1 == occ.index(b): 
      print 'NO SUBLIST' 
      return False 

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

Answer 8

ya los puedes tirar en una versión recursiva de @ solución de NasBanov

def foo(sub, lst): 
    '''Checks if sub is in lst. 

    Expects both arguments to be lists 
    ''' 
    if len(lst) < len(sub): 
     return False 
    return sub == lst[:len(sub)] or foo(sub, lst[1:]) 

Answer 9

La forma más eficaz de hacer esto es usar el Boyer-Moore algorithm, como sugiere Mark Byers. Ya lo hice aquí: Boyer-Moore search of a list for a sub-list in Python, pero pegaré el código aquí. Está basado en el artículo de Wikipedia.

La función search() devuelve el índice de la sublista que se busca, o -1 en caso de error.

def search(haystack, needle): 
    """ 
    Search list `haystack` for sublist `needle`. 
    """ 
    if len(needle) == 0: 
     return 0 
    char_table = make_char_table(needle) 
    offset_table = make_offset_table(needle) 
    i = len(needle) - 1 
    while i < len(haystack): 
     j = len(needle) - 1 
     while needle[j] == haystack[i]: 
      if j == 0: 
       return i 
      i -= 1 
      j -= 1 
     i += max(offset_table[len(needle) - 1 - j], char_table.get(haystack[i])); 
    return -1 


def make_char_table(needle): 
    """ 
    Makes the jump table based on the mismatched character information. 
    """ 
    table = {} 
    for i in range(len(needle) - 1): 
     table[needle[i]] = len(needle) - 1 - i 
    return table 

def make_offset_table(needle): 
    """ 
    Makes the jump table based on the scan offset in which mismatch occurs. 
    """ 
    table = [] 
    last_prefix_position = len(needle) 
    for i in reversed(range(len(needle))): 
     if is_prefix(needle, i + 1): 
      last_prefix_position = i + 1 
     table.append(last_prefix_position - i + len(needle) - 1) 
    for i in range(len(needle) - 1): 
     slen = suffix_length(needle, i) 
     table[slen] = len(needle) - 1 - i + slen 
    return table 

def is_prefix(needle, p): 
    """ 
    Is needle[p:end] a prefix of needle? 
    """ 
    j = 0 
    for i in range(p, len(needle)): 
     if needle[i] != needle[j]: 
      return 0 
     j += 1  
    return 1 

def suffix_length(needle, p): 
    """ 
    Returns the maximum length of the substring ending at p that is a suffix. 
    """ 
    length = 0; 
    j = len(needle) - 1 
    for i in reversed(range(p + 1)): 
     if needle[i] == needle[j]: 
      length += 1 
     else: 
      break 
     j -= 1 
    return length 

Aquí está el ejemplo de la pregunta:

def main(): 
    list1 = [1,0,1,1,1,0,0] 
    list2 = [1,0,1,0,1,0,1] 
    index = search(list1, [1, 1, 1]) 
    print(index) 
    index = search(list2, [1, 1, 1]) 
    print(index) 

if __name__ == '__main__': 
    main() 

Salida:

 
2 
-1 

Answer 10

def sublist(l1,l2): 
    if len(l1) < len(l2): 
    for i in range(0, len(l1)): 
     for j in range(0, len(l2)): 
     if l1[i]==l2[j] and j==i+1: 
     pass 
     return True 
    else: 
    return False