Python: trouvez une liste parmi les membres d'une autre liste (dans l'ordre)

Si j'ai ceci:

a='abcdefghij'
b='de'

Puis ce trouve b:

b in a => True

Est-il un moyen de faire une chose de similaire avec les listes?
Comme ceci:

a=list('abcdefghij')
b=list('de')

b in a => False

Le "Faux" résultat est compréhensible car son, à juste titre, la recherche d'un élément "de", plutôt que (ce que j'arrive à le faire) " d "suivi par un "e"

C'est fonctionne, je sais:

a=['a', 'b', 'c', ['d', 'e'], 'f', 'g', 'h']
b=list('de')
b in a => True

Je peux croquer les données pour obtenir ce que je veux - mais est-il un court Pythonic façon de faire cela?

De préciser: j'ai besoin de préserver l'ordre ici b=['e','d'], doit retourner False).

Et si cela peut aider, ce que j'ai est une liste de listes: ces listes représente tous les chemins possibles (une liste de nœuds visités) à partir du nœud 1 au nœud x dans un graphe orienté: je veux facteur de sortir des chemins communs dans tous les chemins plus longs. (Alors à la recherche de tous les irréductibles 'atomique' les chemins qui constituante tous les chemins plus longs).

Connexes

La meilleure Façon De Déterminer si une Séquence est dans une autre séquence en Python

source d'informationauteur monojohnny

list python

5

Ne sais pas si c'est très pythonic, mais je voudrais le faire de cette façon:
```
def is_sublist(a, b):
    if not a: return True
    if not b: return False
    return b[:len(a)] == a or is_sublist(a, b[1:])
```
Plus courte solution est proposée dans ce discussionmais il souffre des mêmes problèmes que de solutions avec set - il ne considère pas l'ordre des éléments.

Mise à JOUR:

Inspiré par MAK j'ai présenté plus concis et clair version de mon code.

Mise à JOUR:
Il y a des soucis de performance sur cette méthode, en raison de la liste de copie en tranches. Aussi, comme il est récursif, vous pouvez rencontrer limite de la récursivité pour de longues listes. Pour éliminer la copie, vous pouvez utiliser Numpy tranches qui crée des points de vue, pas de copies. Si vous rencontrez des performances ou de la limite de la récursivité questions que vous devriez utiliser la solution sans récursivité.

Je soupçonne qu'il y a plus pythonic façons de le faire, mais au moins, il fait le travail:

l=list('abcdefgh')
pat=list('de')

print pat in l # Returns False
print any(l[i:i+len(pat)]==pat for i in xrange(len(l)-len(pat)+1))

Je pense que ce sera plus rapide - Il utilise C mise en œuvre list.index à la recherche du premier élément, et va à partir de là.

def find_sublist(sub, bigger):
    if not bigger:
        return -1
    if not sub:
        return 0
    first, rest = sub[0], sub[1:]
    pos = 0
    try:
        while True:
            pos = bigger.index(first, pos) + 1
            if not rest or bigger[pos:pos+len(rest)] == rest:
                return pos
    except ValueError:
        return -1

data = list('abcdfghdesdkflksdkeeddefaksda')
print find_sublist(list('def'), data)

Noter que ce renvoie la position de la sous-liste, et pas seulement True ou False. Si vous voulez juste un bool vous pouvez utiliser ceci:

def is_sublist(sub, bigger): 
    return find_sublist(sub, bigger) >= 0

J'ai programmé la solution retenue, ma solution et un nouveau avec un index. L'un avec l'indice est clairement meilleur.

EDIT: j'ai chronométré nosklo la solution, c'est même beaucoup mieux que ce que je suis venu avec. 🙂

def is_sublist_index(a, b):
    if not a:
        return True

    index = 0
    for elem in b:
        if elem == a[index]:
            index += 1
            if index == len(a):
                return True
        elif elem == a[0]:
            index = 1
        else:
            index = 0

    return False

def is_sublist(a, b):
    return str(a)[1:-1] in str(b)[1:-1]

def is_sublist_copylist(a, b):
    if a == []: return True
    if b == []: return False
    return b[:len(a)] == a or is_sublist_copylist(a, b[1:])

from timeit import Timer
print Timer('is_sublist([99999], range(100000))', setup='from __main__ import is_sublist').timeit(number=100)
print Timer('is_sublist_copylist([99999], range(100000))', setup='from __main__ import is_sublist_copylist').timeit(number=100)
print Timer('is_sublist_index([99999], range(100000))', setup='from __main__ import is_sublist_index').timeit(number=100)
print Timer('sublist_nosklo([99999], range(100000))', setup='from __main__ import sublist_nosklo').timeit(number=100)

Sortie en secondes:

4.51677298546

4.5824368

1.87861895561

0.357429027557

2

Donc, si vous n'êtes pas préoccupé par la commande le sous-ensemble apparaît, vous pouvez faire:
```
a=list('abcdefghij')
b=list('de')
set(b).issubset(set(a))

True
```
Modifier après vous préciser: Si vous avez besoin de préserver l'ordre, et la liste est en effet caractères que dans votre question, vous pouvez utiliser:
```
''.join(a).find(''.join(b)) > 0
```

Cela devrait travailler avec ce couple de listes, de la préservation de l'ordre.
Est de vérifier si b est une sous-liste de un

def is_sublist(b,a): 

    if len(b) > len(a):
        return False    

    if a == b:
        return True    

    i = 0
    while i <= len(a) - len(b):
        if a[i] == b[0]:
            flag = True
            j = 1
            while i+j < len(a) and j < len(b):
                if a[i+j] != b[j]:
                    flag = False
                j += 1
            if flag:
                return True
        i += 1
    return False

1
```
>>>''.join(b) in ''.join(a)

True
```
0

Pas sûr de savoir comment la complexité de votre application, mais pour la correspondance de modèle dans les listes, pyparsing est très intelligent et facile à utiliser.
-1

Utiliser les listes' représentation de chaîne et de supprimer les crochets. 🙂
```
def is_sublist(a, b):
    return str(a)[1:-1] in str(b)
```
EDIT: à Droite, il y a des faux positifs ... par exemple is_sublist([1], [11]). Merde réponse. 🙂

Vous devez vous connecter pour publier un commentaire.