提取子序列Python

給定一個數字序列，提取按升序排列的最大長度的子序列。

示例輸入：L = [1,3,5,6,1,5,1,6,7]

輸出：[1,3,5,6]

代碼：

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])

錯誤：

據輸出[1, 2, 3, 4, 1, 2, 4] [1, 2, 4]

但應該輸出：[[1, 2, 3, 4,5] [1, 2, 4, 5]

我該如何解決這個問題？

來源

2016-11-25 Oscar Dolloway

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

我的想法是，它不會工作，你需要重寫它很多。

首先循環播放數字（for i in ...），這非常棒，並且第一個if測試會啓動一系列遞增的數字，到目前爲止確定。但是，您可以將數字同時添加到stored和sequence。爲什麼要同時添加同樣的東西？

然後else觸發，如果序列停止增加。這很酷，你可以按照不斷增加的順序，並注意它何時結束。但是你不相信這一點，而你又用另一個if再次進行完全相同的測試，因爲......原因？在那裏，您刪除sequence。「我會跟蹤所有的序列，當它們結束時，我將把它們扔掉而不使用它們，因爲扔掉我正在尋找的東西就好:)」。

好的，從你給的東西的名字，我猜sequence應該是「我目前的工作序列」。

在那些if測試之後，對於每個循環迭代，檢查len(stored); stored永遠不會被清除或重置，所以它只是建立了原始列表中的幾乎每個數字。一旦你做了這個長度測試......你什麼都不做，除了印刷的東西。

您打印什麼：print('biggest subseq = ', sequence) - 使得它看起來好像是這個名字sequence應該是「最大」，但是這是錯誤的比較，你用它前面的方式。 sequence不是最大的一個，它是當前的一個，對不對？還是不對？「我會使用無用的名字，因爲我不喜歡輸入長名字，爲什麼我的代碼不工作？」。是的，我也一直這樣做。

那你打印那stored是'小分'？什麼是小分支？無論它應該是什麼，stored在這一點上都沒有什麼用處。

而且，你正在跟蹤數字i >= i+1，只有加入i它匹配的時候進行排序的方式，意味着你總是不放過每一個序列中的最後一個號碼。（「下一個更小，所以我會跳過添加這個」）。

和更糟的是，你跟蹤的方式range(len(integers) - 1)意味着你永遠不會檢查原始列表中最後一個數字到最後的子序列中。

所以是的，一個簡單的修復程序將無法用於您的代碼。爲了一個可行的答案，它正沿着正確的方向前進，但完全沒有做正確的事情來實際做到這一點。

我認爲你正在試圖做的是「沿着軌道，直到序列結束，並儲存起來，然後尋找下一個序列。如果是比前一個儲存時間越長，存儲新代替」。所以：

給自己清楚的變量名稱，解釋他們是什麼。
在stored您應該將其設置爲您找到的整個序列的一次，而不是在您看到它們時添加單個數字。
這需要發生在序列結束的地方，而不是輸入列表中的每個數字。
這意味着stored的更新需要在if len(stored) > len(sequence)內發生。
..需要以另一種方式測試 - 是新的比已存儲的更長。
而且它需要採取措施更新商店。

嘗試寫，儘量靠近你的代碼，我可以，讓我這樣的：

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])

，你可以run online at repl.it here。

來源

2016-11-25 21:00:09 TessellatingHeckler

提取子序列Python

回答

相關問題