Comment pouvez-vous déterminer efficacement la présence d’une sous-liste dans une liste plus grande en Python ?

Recherche dans des listes de la présence d'une sous-liste en Python

Identifier la présence d'une sous-liste dans une liste plus grande est une tâche de programmation courante. Python propose une solution simple à ce problème à l'aide d'une fonction personnalisée.

Formulation du problème :

Étant donné deux listes, list1 et list2, déterminez si les éléments de list2 existent comme une séquence contiguë dans list1. Considérez les cas de test suivants :

<code class="python">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])</code>

Implémentation :

Les capacités de programmation fonctionnelle de Python permettent une solution concise utilisant la fonction any() et les compréhensions de liste :

<code class="python">def contains_sublist(lst, sublst):
    n = len(sublst)
    return any((sublst == lst[i:i+n]) for i in range(len(lst)-n+1))</code>

Cette fonction prend deux arguments : lst (la liste principale) et sublst (la sous-liste à rechercher). Il calcule la longueur de sublst et utilise une compréhension de liste pour générer une séquence de plages d'index dans lst. Pour chaque plage, il compare sublst aux éléments correspondants dans lst. Si une correspondance est trouvée, any() renvoie True ; sinon, il renvoie False.

Exemple d'utilisation :

Dans les cas de test fournis, sublistExists(list1, [1,1,1]) renvoie True et sublistExists( list2, [1,1,1]) renvoie False, comme prévu.

Remarque :

La fonction any() optimise la recherche en se terminant à la première correspondance . La fonction a une complexité temporelle de O(m*n), où m est la longueur de lst et n est la longueur de sublst.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!