提取子序列 Python

Question

问题：

给定一个数字序列，提取最大长度的子序列，该子序列按升序排列。

示例输入：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]

我该如何解决这个问题？

Answer 1

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 是 'small sub'？什么是小潜艇？不管它应该是什么，stored 目前没有任何有用的东西。

而且，您跟踪数字 i >= i+1 并且仅在匹配时将 i 添加到序列中的方式意味着您总是会错过每个序列中的最后一个数字。 ("the next one is smaller, so I'll skip adding this one").

更糟糕的是，您跟踪的方式 range( len(integers) - 1) 意味着您永远不会将原始列表中的最后一个数字检查到最终的子序列中。

是的，简单的修复对您的代码不起作用。它正在沿着正确的方向寻找一个可行的答案，但它完全没有做正确的事情来真正做到这一点。

我认为你想做的是 "track along until a sequence ends, and store it. Then, find the next sequence. If that is longer than the previous stored one, store the new one instead"。所以：

给自己一个清楚的变量名，解释它们的用途。
在 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。

提取子序列 Python

extract sub sequence Python

list

subsequence

python-3.5