如何将一个列表分割成单调递增/递减的列表？

Question

如何将一个列表分割成单调递增/递减的列表？

5

我有一个Python列表，其中包含多个单调递减的元素。但是，所有这些序列都不相邻。 A = [[100, 83, 82, 51, 45, 29, 100, 100, 88, 88, 76, 76, 76, 59, 10, 12, 36, 100, 100, 86, 81, 79, 65, 65, 9, 10, 8]]

我想从A提取a1=[100, 83, 82, 51, 45, 29]、a2=[100, 100, 88, 88, 76, 76, 76, 59, 10]、a3=[100, 100, 86, 81, 79, 65, 65, 9]。正如你所看到的，我舍弃了12,36,10,8，因为它们没有遵循任何模式。每个子数组的第一个元素应大于80。因此，我丢弃了以10作为初始元素的单调子数组。到目前为止，我的代码如下。

def chop_array(array):
    itr = 0
    prev_element = 1e6
    window = list()
    mainWindow = list ()
    for i, element in enumerate(array):
        if element <= prev_element:
            window.append(element)
            prev_element = element
        else:
            mainWindow.append(window)
            prev_element = element
            window = list()
            window.append(element)
    filter_array = [True if item[0] > 80  else False for  item in mainWindow]
    return list(itertools.compress(mainWindow,filter_array))

在Python中是否有更有效的方法？

- Spandyie

100,100并不是严格递减的。 - Patrick Artner

1

你能解释一下为什么列表末尾的[10, 8]被舍弃了吗？它形成了一个单调递减的子列表。 - Mustafa Aydın

@MustafaAydın 我已经编辑了描述，每个子数组的最小大小有一个阈值要求。现在假设每个子数组的第一个元素应该是80。 - Spandyie

2个回答

1

有一种方法可以通过将其视为队列来解决这个问题，因为根据索引的下一个记录本质上是我们想要与其他记录进行比较的内容。使用这种方法的另一个好处是，您正在删除记录并重新分配它。因此，在这里不会使内存翻倍。

我要提到的一件事是，使用列表来存储结果列表将是保存进度的快速解决方案。

A = [100, 83, 82, 51, 45, 29, 100, 100, 88, 88, 76, 76, 76, 59, 10, 12, 36, 100, 100, 86, 81, 79, 65, 65, 9, 10, 8]

result = [] # list of lists
r = [] # initialize the logic
r.append(A.pop(0))
while len(A) > 0:
    try:
        # pop the next value
        v = A.pop(0)

        # if its the first value of a sublist, or if its less than the previous record but greater than the next:
        # then add it to the sublist
        if r == [] or (r[-1] >= v and v >= A[0]):
            r.append(v)
        else:
            r.append(v)
            if len(r) > 2:
                result.append(r)
            r = [] # reset the list
    
    # end of the big list, no A[1] to find
    except IndexError as e:
        # add the last one to the r list
        if r[-1] >= v:
            r.append(v)
            if len(r) > 2:
                result.append(r)
        print('reached End of List')
print(result)

- ImTryingMyBest

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mustafa Aydın · Accepted Answer

通过查看与上一项的差异为正的位置，可以检测到每个子列表的起始条目。然后我们可以在这些位置上拆分数组；但由于np.diff将数组大小减小1，因此我们需要在输出中添加1以获得相对于原始数组的索引：

>>> sub_lists = np.split(A, np.where(np.diff(A) > 0)[0] + 1)
>>> sub_lists

[array([100,  83,  82,  51,  45,  29]),
 array([100, 100,  88,  88,  76,  76,  76,  59,  10]),
 array([12]),
 array([36]),
 array([100, 100,  86,  81,  79,  65,  65,   9]),
 array([10,  8])]

需要对此数组列表进行两种类型的过滤：第一种是丢弃只有1个项目的列表，第二种是丢弃第一个项小于80的列表。因此，

>>> result = [sub for sub in sub_lists if sub.size > 1 and sub[0] > 80]
>>> result

[array([100,  83,  82,  51,  45,  29]),
 array([100, 100,  88,  88,  76,  76,  76,  59,  10]),
 array([100, 100,  86,  81,  79,  65,  65,   9])]

我们可以将它们封装在一个函数中：

def split_decreasing(arr, thre=80):
    """
    Splits the given array `arr` into monotonically decreasing subarrays
    of size at least 2 and first entries being at least `thre`.
    """
    split_points = np.where(np.diff(arr) > 0)[0] + 1
    sub_lists = np.split(arr, split_points)
    result = [sub for sub in sub_lists if sub.size > 1 and sub[0] > thre]
    return result

示例运行：

>>> split_decreasing([63, 44, 43, 37, 30, 30, 27, 95, 91, 70, 65, 62, 62, 56, 56])

[array([95, 91, 70, 65, 62, 62, 56, 56])]

>>> split_decreasing(np.arange(10))
[]

>>> split_decreasing([12, 11, 7, 9, 7], thre=80)
[]

>>> split_decreasing([12, 11, 7, 9, 7], thre=10)
[array([12, 11,  7])]

>>> split_decreasing([12, 11, 7, 9, 7], thre=5)
[array([12, 11,  7]), array([9, 7])]

>>> split_decreasing([100, 83, 82, 51, 45, 29, 100, 100, 88, 88, 76, 76, 76,
                      59, 10, 12, 36, 100, 100, 86, 81, 79, 65, 65, 9, 10, 8])

[array([100,  83,  82,  51,  45,  29]),
 array([100, 100,  88,  88,  76,  76,  76,  59,  10]),
 array([100, 100,  86,  81,  79,  65,  65,   9])]