webentwicklung-frage-antwort-db.com.de

Prüfen, ob Liste eine Unterliste ist

Ich muss prüfen, ob list1 eine Unterliste von list2 ist (True; wenn jede mit list1 übliche ganze Zahl in list2 in der gleichen Reihenfolge wie in list1 ist)

def sublist(lst1,lst2):
    for i in range(len(lst1)):
        if lst1[i] not in lst2:
            return False
        for j in range(len(lst2)):
            if (lst1[j] in lst2) and (lst2.index(lst1[i+1]) > lst2.index(lst1[i])):
                return True

Kann mir jemand helfen ... warum funktioniert das nicht?

13
MMM

ich muss prüfen, ob list1 eine Unterliste für list2 ist (True; wenn jede mit list1 gelieferte ganze Zahl in der gleichen Reihenfolge wie in list1 ist)

Ihr Code funktioniert nicht, da ein Listenelement in ls1 nicht in ls2 vorkommt, wird es sofort False zurückgegeben.

Dadurch werden zwei Listen erstellt, die nur die allgemeinen Elemente enthalten (jedoch in der ursprünglichen Reihenfolge) und dann True zurückgeben, wenn sie identisch sind:

def sublist(lst1, lst2):
   ls1 = [element for element in lst1 if element in lst2]
   ls2 = [element for element in lst2 if element in lst1]
   return ls1 == ls2

edit: Eine speichereffiziente Variante:

def sublist(ls1, ls2):
    '''
    >>> sublist([], [1,2,3])
    True
    >>> sublist([1,2,3,4], [2,5,3])
    True
    >>> sublist([1,2,3,4], [0,3,2])
    False
    >>> sublist([1,2,3,4], [1,2,5,6,7,8,5,76,4,3])
    False
    '''
    def get_all_in(one, another):
        for element in one:
            if element in another:
                yield element

    for x1, x2 in Zip(get_all_in(ls1, ls2), get_all_in(ls2, ls1)):
        if x1 != x2:
            return False

    return True
6
L3viathan

Speichereffiziente Lösung basierend auf M. Morgans Antwort. Berücksichtigt, dass, um eine Unterliste zu sein, die Unterliste in der gleichen Reihenfolge in der Superliste gefunden werden muss.

Die Variable k verfolgt die Länge der übereinstimmenden Zeichen. Wenn dies der Länge unserer Unterliste entspricht, können wir true zurückgeben.

Die Variable s verfolgt den Startwert. Ich verfolge dies so, dass ein Testfall wie sublist(["1", "1", "2"],["0", "1", "1", "1", "2", "1", "2"]) mit fremden Wiederholungen des ersten Eintrags den aktuellen Index nicht zurücksetzt, wenn er nicht übereinstimmt. Sobald sich der Startwert ändert, wird s irrelevant, so dass dieser Fall nicht mitten in einem Muster ausgelöst wird.

def sublist(sublist, lst):
    if not isinstance(sublist, list):
        raise ValueError("sublist must be a list")
    if not isinstance(lst, list):
        raise ValueError("lst must be a list")

    sublist_len = len(sublist)
    k=0
    s=None

    if (sublist_len > len(lst)):
        return False
    Elif (sublist_len == 0):
        return True

    for x in lst:
        if x == sublist[k]:
            if (k == 0): s = x
            Elif (x != s): s = None
            k += 1
            if k == sublist_len:
                return True
        Elif k > 0 and sublist[k-1] != s:
            k = 0

    return False
2
Dave Thomas

Eine einfache Möglichkeit, um zu überprüfen, ob alle Elemente einer Liste in einer anderen Liste enthalten sind, konvertiert beide in Mengen:

def sublist(lst1, lst2):
    return set(lst1) <= set(lst2)

Eine andere Möglichkeit, dies zu tun, ist mit collections.Counter. Die zweite Antwort von @ L3viathan ist der effizienteste und schnellste Weg, dies zu tun.

def sublist1(lst1, lst2):
    ls1 = [element for element in lst1 if element in lst2]
    ls2 = [element for element in lst2 if element in lst1]
    return ls1 == ls2


def sublist2(lst1, lst2):
    def get_all_in(one, another):
        for element in one:
            if element in another:
                yield element
    for x1, x2 in Zip(get_all_in(lst1, lst2), get_all_in(lst2, lst1)):
        if x1 != x2:
            return False
    return True


def sublist3(lst1, lst2):
    from collections import Counter
    c1 = Counter(lst1)
    c2 = Counter(lst2)
    for item, count in c1.items():
        if count > c2[item]:
            return False
    return True


l1 = ["a", "b", "c", "c", "c", "d", "e"]
l2 = ["c", "a", "c", "b", "c", "c", "d", "d", "f", "e"]

s1 = lambda: sublist1(l1, l2)
s2 = lambda: sublist2(l1, l2)
s3 = lambda: sublist3(l1, l2)

from timeit import Timer
t1, t2, t3 = Timer(s1), Timer(s2), Timer(s3)
print(t1.timeit(number=10000))  # => 0.034193423241588035
print(t2.timeit(number=10000))  # => 0.012621842119714115
print(t3.timeit(number=10000))  # => 0.12714286673722477

Sein 2. Weg ist um eine Größenordnung schneller, aber ich wollte die Counter-Variante wegen ihrer Verbreitung und Verwendung außerhalb dieses Szenarios erwähnen.

2
Goodies

Mit Iteratoren ist es einfach. 

>>> a = [0,1,2]
>>> b = [item for item in range(10)]
>>> b
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> a
[0, 1, 2]
>>> [False, True][set([item in b for item in a]) == set([True])]
True
>>> a = [11, 12, 13]
>>> [False, True][set([item in b for item in a]) == set([True])]
False
1
Umair Bhatti

b = sublist und a = list suchen dann b durch Aufteilen von a in Längen von b

z.B.

>>> a = [2,4,3,5,7] , b = [4,3]
>>> b in [a[i:len(b)+i] for i in xrange(len(a))]
True

>>> a = [2,4,3,5,7] , b = [4,10]
>>> b in [a[i:len(b)+i] for i in xrange(len(a))]

False
1
codename47

Ich fand, dass das oben genannte ['a', 'b', 'd'] eine Unterliste von ['a', 'b', 'c', 'e', ​​'d'] war wahr, obwohl alle Elemente der Unterliste in der Liste vorhanden sind. Um die Reihenfolge aufrechtzuerhalten, kam ich auf:

def sublist4(sublist,lst):
    #Define an temp array to populate 
    sub_list=[]
    comparable_sublist=[]
    #Define two constants to iterate in the while loop
    i=0
    k=0
    #Loop the length of lst
    while i < len(lst):
        #If the element is in the sublist append to temp array, 
        if k < len(sublist) and lst[i] == sublist[k]:
            sub_list.append(lst[i])
            #set a comparable array to the value of temp array
            comparable_sublist = sub_list
            k += 1
            #If the comparable array is the same as the sublist, break
            if len(comparable_sublist) == len(sublist):
                break

        #If the element is not in the sublist, reset temp array
        else:
            sub_list = []


        i += 1

    return comparable_sublist == sublist

Obwohl dies nicht sehr speichereffizient ist, finde ich, dass es mit kleinen Listen gut funktioniert.

1
M. Morgan
def sublist(l1,l2):
    s1=" ".join(str(i) for i in l1)
    s2=" ".join(str(i) for i in l2)
    if s1 in s2:
        return True
    else:
        return False
0
Sanjana Mantri

Ich habe einen kurzen Weg gefunden, um nach Unterlisten zu suchen

lst1=[1,2,5,6,8,3,2,34,3,4]
lst2=[1,2,3,4]


def sublist(lst1,lst2):
    for item in lst2:
        try:
           lst1.index(item)
        except ValueError:
           return False
     return True


 print(sublist(lst1,lst2))

was ich getan habe, ist im Grunde genommen 2 Listen. lst1 ist die größere Liste und lst2 ist die Unterliste, nach der wir suchen. Dann nehme ich jedes Element von lst2 und prüfe, ob es in lst1 ist, indem ich nach seinem Index suche 

wenn es nicht einmal einen einzelnen Artikel finden kann, wird False zurückgegeben

wenn alle Elemente abgedeckt sind, wird True zurückgegeben 

0
Mohan Ram

Eine andere Möglichkeit besteht darin, alle möglichen Unterlisten zu durchsuchen und zurückzukehren, sobald eine Übereinstimmung gefunden wurde

def is_sublist(ys, xs):
    for i in range(len(xs) - len(ys)):
        if xs[i:i + len(ys)] == ys:
            return True
    return False
0
Jarno

Probier diese!! Unterliste y fehlt die Reihenfolge von Liste x nicht.

x = Liste 

y = Unterliste

if ([i for i,j in enumerate(y) for k,l in enumerate(x) if i == k and j!=l]):
    print("True")
else:
    print("False")
0
def has_ordered_intersection(xs, ys):
    common = {*xs} & {*ys}
    return all(x == y for x, y in Zip((x for x in xs if x in common),
                                      (y for y in ys if y in common)))

Dies besteht @ L3viathans Doktest mit weniger Codezeilen, wobei eine ähnliche Strategie wie bei der "speichereffizienten Variante" und mit wohl größerer Gesamteffizienz angewendet wird.

>>> has_ordered_intersection([], [1,2,3])
True
>>> has_ordered_intersection([1,2,3,4], [2,5,3])
True
>>> has_ordered_intersection([1,2,3,4], [0,3,2])
False
>>> has_ordered_intersection([1,2,3,4], [1,2,5,6,7,8,5,76,4,3])
False

Ich habe die Schnittmenge anstelle eines Generators verwendet, weil ich denke, dass der zusätzliche Speicher ein guter Kompromiss im Vergleich zu den Zeitkosten für das Scannen der gesamten Liste pro Element ist (was in für eine Liste tut), insbesondere wenn sie sind lang.

Ich denke auch nicht, dass dies eine "Unterliste" genannt werden sollte, da xs Elemente haben darf, die ys nicht hat. Die obige Beziehung ist symmetrisch: Das Vertauschen der Argumente ändert nichts an der Antwort. Eine wirklich geordnete "Unterliste" wäre nicht symmetrisch und würde eher so aussehen

def is_ordered_sublist(xs, ys):
    xset = {*xs}
    return all(x == y for x, y in Zip(xs, (y for y in ys if y in xset)))
0
gilch

Eine andere einfache Möglichkeit ist die Verwendung von List Verständnis Verwenden Sie die integrierte Funktion All , um zu überprüfen, ob alle Elemente in Liste1 in Liste2 enthalten sind.

Beispiel:

list1 = ['1','2']
list2 = ['1','2',3]

all(i in list2 for i in list1)
0