Python - prüfen ob Liste ein einer anderen Liste ist

[M. H. (mophzk)]

Hallo Zusammen,

ich habe eine Liste voller Tupel. Jetzt möchte ich prüfen, ob eine 
zweite (kleinere) Liste in der ersten Liste vorhanden ist.

Beispiel:

liste1 = [(1, 0), (0, 0), (0, 1), (1, 1), (0, 1), (0, 0), (1, 1), (1, 1), (0, 0), (1, 0), (0, 0), (1, 0), (0, 1), (1, 1)] 

liste2 =  [(0, 1), (1, 1), (0, 1)]

Gibt es eine Möglichkeit herauszufinden ob liste2 in liste1 enthalten 
ist, ohne die ganze Liste in Schleifen zu durchlaufen. Also sowas wie 
ein  regulärer Ausdruck oder ähnliches?


Danke im voraus.
Mopzhk

[Schlange (Gast)]

if list2 in list1:

[M. H. (mophzk)]

Hallo Schlange,
danke für deine Antwort.

Schlange schrieb:
> if list2 in list1:

Das hab ich auch schon getestet:

data = []
status =[]
on = (1,0)
off = (1,1)
i = 0

while i != 2:
  i += 1
  status.append(on)
  status.append(off)
  
i = 0  
while i != 10:
  i += 1
  data.append(on)
  data.append(off)
  
if status in data:
  print("Gefunden")
else:
  print("nicht Gefunden")

jedoch mit dem Ergebnis "nicht Gefunden".

Gruß Mophzk

[Yalu X. (yalu) (Moderator)]

Eine Funktion, die prüft, ob eine Liste eine Teilliste einer anderen
Liste ist, gibt es in Python und seiner Standardbibliothek m.W. nicht.

Es bleibt also wohl nichts anderes übrig, als eine entsprechende
Funktion selber zu schreiben.

Der in-Operator prüft, ob der linke Operand ein Element des rechten
Operanden ist, also bspw.

  [2,3] in [[1,2], [2,3], [3,4]] -> True

Das ist aber nicht, wonach du suchst.

[Theor (Gast)]

Mit Vorbehalt, denn ich bin nicht umfassend erfahren in Python.

Also, geht man Python 3.7 aus (und vermutlich verhalten sich frühere 
Versionen genau so), dann prüft der "in" Operator, ob sich ein Objekt 
in einer Liste befindet. 
https://docs.python.org/3/reference/expressions.html#membership-test-operations

Man wird das, vermute ich, selber implementieren müssen. Ist aber auch 
nicht schwierig, denke ich, wenn man auf die Ausführungsgeschwindigkeit 
nicht all zu viel Wert legt. Aber eine Suche nach einer fertigen 
Funktion mag sich lohnen.

[Walter T. (nicolas)]

Wenn es um die Elemente und nicht um die Anzahl geht, wäre eine 
Konvertierung in ein set eine Möglichkeit.

[Egon D. (Gast)]

Theor schrieb:

> Man wird das, vermute ich, selber implementieren müssen.
> Ist aber auch nicht schwierig, denke ich, wenn man auf
> die Ausführungsgeschwindigkeit nicht all zu viel Wert
> legt.

Wenn die Listen sortiert sind, genügt ein Durchlauf der
längeren Liste.
Falls sie nicht sortiert sind, gibt es bestimmt eine
einigermaßen effiziente Sortierroutine als Standard-
funktion.

[mh (Gast)]

M. H. schrieb:
> Gibt es eine Möglichkeit herauszufinden ob liste2 in liste1 enthalten
> ist, ohne die ganze Liste in Schleifen zu durchlaufen.

Zuerst musst du einmal genau definieren was mit "liste2 in liste1" 
gemeint ist.
Aus dem Rest deines 1. Beitrags und dem 2. gehe ich davon aus du meinst 
"Elemente aus liste2 in liste1", liste2 ist also keine Liste aus Listen. 
Weitere Fragen:
-Ist die Position in liste2 relevant, also sowas wie Reihenfolge?
-Was ist wenn Elemente in liste1 mehrfach vorkommen? Müssen dann auch 
mehrere in liste2 vorhanden sein?
-Sind die Elemente tatsächlich Integer-Tuple, oder ist dein Quelltext 
ein Beispiel? Wenn es nur ein Beispiel ist, lassen sich die Elemente 
sortieren?

[Florian F. (flof3000)]

Wenn es nur um die Frage geht 'sind alle Elemente aus Liste2 in Liste1 
auch mindestens 1 mal vorhanden:

len(set(list1).intersection(list2)) == len(list2)

Laufzeit: O(n).

[imonbln (Gast)]

Das set ist dein freund es hat eine issubset Funktion die das macht was 
du willst. folgender Code sollte "Sublist found" ausgeben. Das 
Konvertieren der beiden listen in ein Set macht Python für dich.

 list1 = [(1, 0), (0, 0), (0, 1), (1, 1), (0, 1), (0, 0), (1, 1), (1, 1), (0, 0), (1, 0), (0, 0), (1, 0), (0, 1), (1, 1)] 
 list2 = [(0, 1), (1, 1), (0, 1)]

 if set(list2).issubset(list1): 
    print('Sublist found')
 else:
    print('not found')

[Theor (Gast)]

Egon D. schrieb:
> Theor schrieb:
>
>> Man wird das, vermute ich, selber implementieren müssen.
>> Ist aber auch nicht schwierig, denke ich, wenn man auf
>> die Ausführungsgeschwindigkeit nicht all zu viel Wert
>> legt.
>
> Wenn die Listen sortiert sind, genügt ein Durchlauf der
> längeren Liste.
> Falls sie nicht sortiert sind, gibt es bestimmt eine
> einigermaßen effiziente Sortierroutine als Standard-
> funktion.

Es ist natürlich nur eine Vermutung, aber ich gehe davon aus, dass die 
Abfolge der Elemente in beiden Listen eine Rolle spielt, weil

1. der TO die Listen nicht sortiert hat und
2. Elemente mehrfach vorkommen und
3. der TO mit dem Wort "in" das "Enthaltensein" einer Liste in einer 
anderen assoziiert (in seinem Beitrag) anstelle des Enthaltenseins der 
Elemente der Liste oder des enthaltenseins einer Liste in einer Liste 
von Listen. (Das kann natürlich auch ein fehlgeschlagener Versuch des 
prägnanten Ausdrucks sein).

Insofern, gehe ich davon aus, dass die Listen auf keinen Fall sortiert 
sein sollen.
Andernfalls hast Du natürlich durchaus recht, diesen Aspekt zu nennen.
Aber danach hat ja noch jemand gefragt. Mal abwarten.

[M. H. (mophzk)]

Theor schrieb:

> Es ist natürlich nur eine Vermutung, aber ich gehe davon aus, dass die
> Abfolge der Elemente in beiden Listen eine Rolle spielt, weil

Das ist richtig.

Die einfachste Lösung für ich war es die beiden Listen in Strings zu 
schreiben und dann mit

if liste2 in liste1:

zu überprüfen.

Aber Danke für eure Hilfe. Sollte ich die Zeit finden, werde ich mich 
nach einer eleganteren Möglichkeit umsehen.

Grüße Mophzk

[Egon D. (Gast)]

Theor schrieb:

> 1. der TO die Listen nicht sortiert hat und
> 2. Elemente mehrfach vorkommen und
> 3. der TO mit dem Wort "in" das "Enthaltensein" einer
> Liste in einer anderen assoziiert (in seinem Beitrag)
> anstelle des Enthaltenseins der Elemente der Liste
> oder des enthaltenseins einer Liste in einer Liste von
> Listen. (Das kann natürlich auch ein fehlgeschlagener
> Versuch des prägnanten Ausdrucks sein).

Ach so. Ich hatte "...ist ... in ... enthalten" als
TeilMENGENbeziehung aufgefasst.

Wenn ich Dich richtig verstehe, wollte der TO aber
wissen, ob Liste2 eine TeilLISTE von Liste1 ist, also
ob Liste1 in der Form "Präfixliste Liste2 Suffixliste"
darstellbar ist.

Das habe ich dann missverstanden. Entschuldigung.

[Falk Z. (lab-coding-de)]

Wäre das eventuell eine mögliche Lösung der Aufgabenstellung:

list1 = [(1, 0), (0, 0), (0, 1), (1, 1), (0, 1), (0, 0), (1, 1), (1, 1), (0, 0), (1, 0), (0, 0), (1, 0), (0, 1), (1, 1)]
list2 =  [(0, 1), (1, 1), (0, 1)]

n_elements = len(list2)

for i in range(len(list1) - n_elements):
    if list1[i:i + n_elements] == list2:
        print('Found at index {0}...'.format(i))
        break
else:
    print('Not found...')

Viele Grüße
Falk

[Sheeva P. (sheevaplug)]

M. H. schrieb:
> if status in data:

Alter!

[Sheeva P. (sheevaplug)]

Yalu X. schrieb:
> Der in-Operator prüft, ob der linke Operand ein Element des rechten
> Operanden ist, also bspw.
>
>
>

>   [2,3] in [[1,2], [2,3], [3,4]] -> True
>

>
> Das ist aber nicht, wonach du suchst.

Sucht der TO möglicherweise nach list(set(liste1) & set(liste2))?

[Theor (Gast)]

Egon D. schrieb:

> [...]
> Ach so.
> [...]
> Das habe ich dann missverstanden. Entschuldigung.

Macht ja nix. Das nächste Mal, verstehe ich was falsch. :-)