Prüfen, ob eine Liste innerhalb einer anderen Liste existiert?

Question

Grundsätzlich kann ich sagen, ich habe:

>>> a = [1,3,2,2,2]
>>> b = [1,3,2]

Ich möchte sehen, ob alle Elemente in b in a vorhanden sind, und zwar in der gleichen Reihenfolge. Für das obige Beispiel würde b also innerhalb von a existieren.

Ich hoffe irgendwie, dass es eine wirklich einfache Antwort in einer Zeile gibt.

Answer 1

Dies ist ein einfacher O(n * m)-Algorithmus:

any(a[i:i + len(b)] == b for i in range(len(a) - len(b) + 1))

Beachten Sie, dass dies nicht der schnellste Weg ist, dies zu tun. Wenn Sie eine hohe Leistung benötigen, können Sie ähnliche Techniken verwenden wie in String-Suchalgorithmen .

Answer 2

Wenn Sie mit "in der gleichen Reihenfolge" eine Teilfolge (im Gegensatz zu einer Teilzeichenkette) meinten, dann sollte dieser Nicht-Einzeiler schnell funktionieren:

  def is_subsequence(x, y):
    i, j = 0, 0
    while i < len(x) and j < len(y):
      if x[i] == y[j]:
        i += 1
      j += 1
    return i == len(x)

Answer 3

Hier ist eine Lösung, die für Listen von Ints funktioniert.

Verwandeln Sie zum Beispiel [1, 3, 2] in die Zeichenkette "'1', '3', '2'". Verwenden Sie dann die eingebaute String-Inklusion, um zu sehen, ob sie in der anderen Liste enthalten ist.

repr(map(str, b))[1:-1] in repr(map(str, a))[1:-1]

Answer 4

Das ist wahrscheinlich nicht sehr effizient, aber man könnte es verwenden:

In [1]: a = [1,3,2,2,2]

In [2]: b = [1,3,2]

In [3]: b == [val for val in a if val in b]
Out[3]: False

In [4]: a = [6,1,3,2,5,4]

In [5]: b == [val for val in a if val in b]
Out[5]: True

Der erste Test ergibt False wegen der Duplikate von 2 . Die Frage ist, wie Sie mit Duplikaten im Allgemeinen umgehen wollen. Wenn Sie sie nur am Ende abschneiden wollen, können Sie die Liste auf die Länge von a :

In [6]: a = [1,3,2,2,2]

In [7]: b == [val for val in a if val in b][:len(b)]
Out[7]: True

Answer 5

Es tut mir leid, aber was Sie tun wollen, ist im Grunde das gleiche wie String-Matching (wenn auch mit Listen anstelle von Strings). Sie sollten sich vielleicht Folgendes ansehen Knuth-Morris-Pratt o Boyer Moore für einen linearen Zeitalgorithmus.

EDITAR:
Ich gehe davon aus, dass Sie mit "in der Reihenfolge" meinen, dass sie an einer beliebigen Stelle in der Abfolge aufeinander folgen. Wenn sie durch andere Elemente dazwischen getrennt werden können, dann ist dies nicht die Lösung, die Sie wollen.