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

Question

假设您有以下列表

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

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

Answer 1

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

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

随心所欲

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

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

Smallest number of increasing sequences that contain all elements of a list

python

algorithm

sequence

python-3.x