extrahieren Untersequenz Python

Question

Frage:

Geben Sie eine Sequenz von Zahlen, extrahieren Sie die Untersequenz der maximalen Länge, die in aufsteigender Reihenfolge ist.

Beispiel Eingabe: L = [1,3,5,6,1,5,1,6,7]

Ausgang: [1,3,5,6]

Code:

def Sequence(integers): 


sequence = [] 
i = 0 
stored = [] 
#newseq = [] 

for i in range(len (integers)-1) : 

    if integers[i] <= integers[i+1]: #i less than i+1 append to sequence 
     stored.append(integers[i]) 
     sequence.append(integers[i]) 

    else: 
     if integers[i] >= integers[i+1]: 

      del sequence[:] 

    if len(stored) > (len(sequence)): 
     print('biggest subseq =',stored) 
     print('small sub',sequence) 

print (stored,sequence) 

Sequence([1,2,3,4,5,1,2,4,5]) 

Fehler:

Es ist die Ausgabe [1, 2, 3, 4, 1, 2, 4] [1, 2, 4]

Aber es sollte die Ausgabe sein: [[1, 2, 3, 4,5] [1, 2, 4, 5]

Wie kann ich das beheben?

Answer 1

once this works I can display the biggest subsequence. any ideas?

Meine Idee ist, dass es nicht funktionieren, müssen Sie es ziemlich viel neu zu schreiben.

Sie beginnen mit dem Durchlaufen der Zahlen (for i in ...), was großartig ist, und der erste if Test nimmt eine Serie von steigenden Zahlen auf, OK bis jetzt. Aber dann fügen Sie die Nummern zu stored und sequence hinzu. Warum fügen Sie beiden dasselbe hinzu?

Dann wird die else ausgelöst, wenn die Sequenz aufhört zu erhöhen. Das ist cool, du kannst einer zunehmenden Sequenz folgen und bemerken, wenn sie endet. Aber du vertraust das nicht, und du machst genau denselben Test nochmal mit einem anderen if, weil ... Gründe? Dort löschen Sie sequence. "Ich werde alle Sequenzen verfolgen, und wenn sie enden, werde ich sie wegwerfen, ohne sie zu benutzen, weil das Wegwerfen der Dinge, die ich suche, einfach in Ordnung ist.".

OK, von den Namen, die Sie die Dinge gegeben haben, denke ich sequence sollte "die aktuelle Sequenz Ich arbeite an".

Nach diesen if Tests, für jede Schleife Iteration, überprüfen Sie len(stored); stored wird nie gelöscht oder zurückgesetzt, so dass es fast jede Nummer in der ursprünglichen Liste aufbaut. Sobald du diesen Längen-Test machst ... machst du nichts, außer Dinge zu drucken.

Was Sie drucken: print('biggest subseq = ', sequence) - macht es wie der Name aussehen sequence soll die „größte“ sein, aber das ist falsch im Vergleich zu dem, wie Sie es früher verwendet. sequence ist nicht die größte, es ist die aktuelle, oder? Oder nicht richtig? "Ich werde nicht hilfreiche Namen verwenden, weil ich nicht gerne lange Namen schreibe. Warum funktioniert mein Code nicht?". Ja, das mache ich auch die ganze Zeit.

Dann drucken Sie, dass stored das 'kleine Unter' ist? Was ist ein kleines Sub? Was auch immer es sein soll, stored hält nichts nützliches an dieser Stelle.

Und die Art, wie Sie die Nummern i >= i+1 verfolgen und nur i hinzufügen, wenn es übereinstimmt, bedeutet, dass Sie immer die letzte Nummer in jeder Sequenz verpassen. ("Der nächste ist kleiner, also werde ich diesen hinzufügen").

und schlimmer, die Art, wie Sie verfolgen range(len(integers) - 1) bedeutet, dass Sie nie die allerletzte Nummer in der ursprünglichen Liste in die endgültige Teilsequenz überprüfen.

Also ja, eine einfache Lösung wird nicht für Ihren Code arbeiten. Es geht in die richtige Richtung für eine praktikable Antwort, aber es macht absolut nicht die richtigen Dinge, um es tatsächlich zu tun.

---

denke ich, was Sie versuchen, zusammen ist „Track zu tun, bis eine Sequenz endet, und speichern Sie es. Dann die nächste Sequenz finden. Wenn das länger als die vorherige gespeichert ist, speichern Sie die neue stattdessen". Also:

1. Geben Sie sich klare Variablennamen, die erklären, was sie sind.

2. In stored sollten Sie es einmal auf die gesamte Sequenz, die Sie gefunden haben, setzen, nicht einzelne Zahlen hinzufügen, wie Sie sie sehen.

3. Das muss an dem Punkt geschehen, an dem die Sequenz endet, nicht für jede Nummer in der Eingabeliste.

4. Das bedeutet, dass das Update für stored innerhalb if len(stored) > len(sequence) erfolgen muss.

5. .. welches anders getestet werden muss - ist das neue länger als das gespeicherte.

6. Und es muss Maßnahmen ergreifen, um den Laden zu aktualisieren.

Der Versuch, das zu schreiben, so nah an Ihrem Code, wie ich kann, wird mir dies:

def Sequence(integers): 

    longest_sequence = [] 
    current_sequence = [] 

    for i in range(len(integers)): 

    if i < len(integers) - 1 and integers[i] <= integers[i+1]: # sequence continues 
     current_sequence.append(integers[i]) 
     print('current_sequence ', current_sequence) 

    else:       # else sequence, or input, ends now 
     current_sequence.append(integers[i]) # catch this last number in sequence, too 
     print('\nsubseq ended ', current_sequence) 

     # now we've hit the end of a subsequence 
     # do we replace the stored one, or not? 
     if len(current_sequence) > len(longest_sequence): 
     print('\nreplacing previous longest ', longest_sequence) 

     longest_sequence = current_sequence 

     # either way, reset the current sequence tracker 
     current_sequence = [] 

    print() 
    print ('Finished. Longest found: ', longest_sequence) 


Sequence([1,2,3,4,5,1,2,4,5]) 
print('\n----\n') 
Sequence([1,2,4,5,1,2,3,4,5]) 

dem Du run online at repl.it here.