Comment tester si une liste contient une autre liste ?

Question

Comment puis-je tester si une liste contient une autre liste (c'est-à-dire qu'il s'agit d'une sous-séquence contiguë). Disons qu'il y avait une fonction appelée contient :

 contains([1,2], [-1, 0, 1, 2]) # Returns [2, 3] (contains returns [start, end])
contains([1,3], [-1, 0, 1, 2]) # Returns False
contains([1, 2], [[1, 2], 3]) # Returns False
contains([[1, 2]], [[1, 2], 3]) # Returns [0, 0]

Éditer:

 contains([2, 1], [-1, 0, 1, 2]) # Returns False
contains([-1, 1, 2], [-1, 0, 1, 2]) # Returns False
contains([0, 1, 2], [-1, 0, 1, 2]) # Returns [1, 3]

Answer 1

Si tous les éléments sont uniques, vous pouvez utiliser des ensembles.

 >>> items = set([-1, 0, 1, 2])
>>> set([1, 2]).issubset(items)
True
>>> set([1, 3]).issubset(items)
False

Answer 2

Il existe une fonction all() et any() pour ce faire. Pour vérifier si big contient TOUS les éléments dans small

 result = all(elem in big for elem in small)

Pour vérifier si small contient TOUS les éléments dans big

 result = any(elem in big for elem in small)

le résultat de la variable serait booléen (TRUE/FALSE).

Answer 3

Puis-je humblement suggérer l' algorithme Rabin-Karp si la liste big est vraiment longue. Le lien contient même du code presque utilisable en presque Python.

Answer 4

Cela fonctionne et est assez rapide car il effectue la recherche linéaire à l'aide de la méthode intégrée list.index() et de l'opérateur ==

 def contains(sub, pri):
    M, N = len(pri), len(sub)
    i, LAST = 0, M-N+1
    while True:
        try:
            found = pri.index(sub[0], i, LAST) # find first elem in sub
        except ValueError:
            return False
        if pri[found:found+N] == sub:
            return [found, found+N-1]
        else:
            i = found+1