时间戳

首页 > 解决方案 > 包含列表所有元素的最小递增序列数

python - 包含列表所有元素的最小递增序列数

问题描述

假设您有以下列表

a_list = [1, 2, 3, 4, 8, 7, 6]

我们希望从列表的任一侧找到包含列表所有元素的递增序列的最小“数量” 。

对于上面的例子，我们会得到

序列 = [[1,2,3,4,8], [6,7]]

答案为2 。这是因为我们可以形成一个从左到右的递增序列[1,2,3,4,8]。我们也可以形成一个从右到左的递增序列[6,7]。

我考虑过创建两个列表，它们给出列表的所有递增序列和列表的反向，因此

left_to_right = [[1,2,3,4,8],[7], [6]]
right_to_left = [[6,7,8], [4], [3], [2], [1]]

但我不知道从那里去哪里。有什么想法吗？

标签： pythonpython-3.xalgorithmsequence

解决方案

编辑：下面的原件不必要地复杂。“从左边”增加只是意味着减少。因此，只需遍历列表一次，使用布尔标志跟踪递增和递减序列，使它们尽可能长，然后在最后计数。这应该有效。未测试。

increasing = None
current_item = _list[0]
all_sequences = []
current_sequence = [_list[0]]

for item in _list[1:]:
    if increasing is None:
        increasing = item > current_sequence[-1]
        current_sequence.append(item)

    elif (item > current_item and increasing) or (item < current_item and not increasing):
        current_sequence.append(item)

    elif (item > current_item and not increasing) or (item < current_item and increasing):
        all_sequences.append(current_sequence)
        current_sequence = [item]
        increasing = None
    
    current_item = item
all_sequences.append(current_sequence)
result = len(all_sequences)

原始答案：这里有一些想法

首先，我假设您的函数将始终使序列尽可能长。所以你得到这个：

left_to_right = [[1,2,3,4,8],[7], [6]]

而不是，例如，这个：

left_to_right = [[1,2],[3],[4,8],[7], [6]]

（从技术上讲，这也是一个递增序列的列表）。

您的下一项工作是确保您获得列表中的所有数字。所以你必须选择一些递增的序列。您选择的序列越长，您在不添加太多序列的同时“用完”的数字就越多。举个例子：

left_to_right = [[1,2,3,4,8],[7], [6]]
right_to_left = [[6,7,8], [4], [3], [2], [1]]

将两个列表连接在一起：

all = left_to_right + right_to_left

现在找到最长的序列：

longest = max(all, key=lambda x:len(x))

那会给你

[1,2,3,4,8]

现在重复，抓住下一个最长的序列，继续前进，直到你捕捉到列表中的所有数字。那会给你：

[[1,2,3,4,8], [6,7,8]]

作为最后一步，检查重复项。然后你会得到

[[1,2,3,4,8], [6,7]]

如预期的

我怀疑这应该总是给你最少的序列。但也许如果有重复我可能是错的。

推荐阅读