确定输入的列表是否严格递增。

Question

我正在尝试确定输入列表是否为严格递增的列表。此外，如果从列表中仅删除一个元素会导致严格递增的列表，则仍将考虑列表为真。以下是我的代码。它似乎有索引错误，但我不理解为什么。

 def almostIncreasingSequence(sequence):
    n=len(sequence)
    count=0
    if n<=2:
        return True

    for i in range (n-1):
        #test if the i-th element is bigger or equal to the elements after it. If it is, remove that element, and add one to count 
        for j in range (i+1,n):
            if sequence[i]>=sequence[j]:
                sequence.pop(i)
                count+=1
    #if there is more than one element that has to be taken out, it's false           
    if count>1:
        return False

    return True

- M-M

---

你必须（或者应该）实际上删除一个有问题的项目吗？一次单独的计数，计算 sequence[i] > sequence[i+1] 的数量就足够了。 - chepner

你遇到了 IndexError 是因为在缩小列表的过程中迭代了该列表，所以 for i in range(n-1): 语句是无效的。 - Alex Hall

你的函数只返回 True 或 False；我的问题是，sequence 是否也要作为副作用变成单调递增序列？ - chepner

如果不需要变异，您只需要计算递减步数，并在 count < 2 时返回 true；在您的示例中 count = 1，因为 sequence[0] > sequence[1]，但是 sequence [1] < sequence[2] < sequence[3] < sequence[4]。 - chepner

@chepner，没有要求改变序列使其单调递增。 - M-M

Answer 1

好的，事实证明这个问题并不容易。

如果您想要一个高效的解决方案，我认为您最好使用类似于最长递增子序列问题的算法。

但是，在这里，我们不关心实际的最长递增子序列 - 我们只需要它的长度。此外，如果我们已经执行了n次插入（其中n是我们对“无序”元素数量的限制），则在维护有序列表时，我们可以进行短路处理。

这也很好地推广到n元素“几乎递增”的情况，并且在最坏的情况下，在大小为M-n-1到M的列表上执行n-1次二分搜索。

import bisect

def almost_increasing(li, n=1):
    if len(li) < 2:
        return True
    ordered_li = [li[0]]
    violator_count = 0
    for ele in li[1:]:
        if ele < ordered_li[0]:
            violator_count += 1
            ordered_li[0] = ele
        elif ele > ordered_li[-1]:
            ordered_li.append(ele)
        else:
            violator_count += 1
            insertion_pos = bisect.bisect_right(ordered_li, ele)
            ordered_li[insertion_pos] = ele
        if violator_count > n: return False
    return True

这个算法的思想如下：

我们遍历列表，同时维护一个有序子序列。

当我们到达一个新元素时，

如果该元素无法附加到我们的有序子序列上，则它是增量属性的“违规者”。我们随后使用二分搜索bisect将其插入正确位置的有序子序列中。

否则，我们只需将其附加到我们的有序子序列中并继续进行。

在每次迭代结束时，如果我们已经有太多的违规者，我们可以短路退出。否则，在循环完成后，我们保证拥有一个长度在原始列表长度的n之内的递增子序列。

---

演示

>>> almost_increasing([5, 1, 2, 3, 4])
True
>>> almost_increasing([1, 2, 5, 2, 15, 0, 176])
False
>>> almost_increasing([1, 2, 5, 2, 15, 0, 176], 2)
True

- miradulo

---

我会让数学问题由你来解决，但是相对于这个答案的O(n log(n))，我的答案应该是O(n)吧？ - G_M

@DeliriousLettuce 让我理解一下你的想法，给我一分钟 :) - miradulo

@DeliriousLettuce 嗯，你的看起来是正确的！它不会扩展到“n”-off情况（当然，这不是问题的一部分）。我在质疑你是否需要“a，b，c，d”，难道你不能只限制于“a，b，c”吗？我也不认为我的实际上是“O(n log(n))”，因为二分搜索只能发生“k”次，其中“k”是第二个参数。需要再思考一下。 - miradulo

@DeliriousLettuce 我怀疑 n-off 不能像我的解决方案那样在不维护完全排序的情况下工作，但请告诉我！我运行了一些基准测试，对于更大的数据（都比Adam的要好），我的解决方案似乎比你的稍微快一点，可能是因为比较次数较少。由于存在很多变量，所以很难进行基准测试。这是一个有趣的问题。 - miradulo

再次感谢您对多余变量的见解，它让我能够简化我的答案。现在看起来更简单易读了。我认为您关于n-off问题的观点是正确的，我的解决方案并不适用于它。之前忘记给您点赞了，但+1并再次感谢您的解决方案和时间！ - G_M

Answer 2

def almost_increasing_sequence(sequence):
    if len(sequence) < 3:
        return True

    a, b, *sequence = sequence
    skipped = 0
    for c in sequence:
        if a < b < c:  # XXX
            a, b = b, c
            continue
        elif b < c:    # !XX
            a, b = b, c
        elif a < c:    # X!X
            a, b = a, c
        skipped += 1
        if skipped == 2:
            return False
    return a < b


if __name__ == '__main__':
    assert almost_increasing_sequence([]) is True
    assert almost_increasing_sequence([1]) is True
    assert almost_increasing_sequence([1, 2]) is True
    assert almost_increasing_sequence([1, 2, 3]) is True
    assert almost_increasing_sequence([3, 1, 2]) is True
    assert almost_increasing_sequence([1, 2, 3, 0, 4, 5, 6]) is True
    assert almost_increasing_sequence([1, 2, 3, 0]) is True
    assert almost_increasing_sequence([1, 2, 0, 3]) is True
    assert almost_increasing_sequence([10, 1, 2, 3, 4, 5]) is True
    assert almost_increasing_sequence([1, 2, 10, 3, 4]) is True
    assert almost_increasing_sequence([1, 2, 3, 12, 4, 5]) is True

    assert almost_increasing_sequence([3, 2, 1]) is False
    assert almost_increasing_sequence([1, 2, 0, -1]) is False
    assert almost_increasing_sequence([5, 6, 1, 2]) is False
    assert almost_increasing_sequence([1, 2, 3, 0, -1]) is False
    assert almost_increasing_sequence([10, 11, 12, 2, 3, 4, 5]) is False

- G_M

---

[1, 2, 3, 12, 4, 5] 怎么样？ - miradulo

@JingLi 我已经更新了你的测试用例、miradulo的测试用例以及我自己的一些测试用例。如果这段代码是正确的，那么它似乎是最有效的解决方案，因为它只需要一次序列遍历，也不使用任何导入。 - G_M

@Delirious Lettuce，当长度大于3时，我不明白你将序列设置为什么？d是什么？ - M-M

@JingLi 我正在将sequence的前三个元素分割为a，b，c，然后开始迭代剩下的sequence。虽然miradulo指出，我认为我可以只使用a，b，c而不是a，b，c，d。如果你给我几分钟，我会尝试提取第四个变量d并简化代码。 - G_M

@JingLi 这取决于你使用的Python版本。我使用的是Python 3.6.4编写的代码，在这种情况下，它会将sequence中剩余的元素（在去除前两个元素后）解包到一个名为sequence的变量中。在Python 2中，这将导致SyntaxError错误，但有几种不同的方法可以实现相同的效果（其中一种方法是使用iter，在以下链接中有示例）。这是相同的示例在Python 3.6.4和Python 2.7.12中。更多信息可以在这个PEP中找到。 - G_M

Answer 3

如果你在Python中写了for i in range(len(some_list))，那么你可能做错了。这就是为什么它失败的原因。n是处理之前序列的长度，但是当你从列表中pop项时，长度会发生变化。

更好的方法是比较需要删除的索引标记，并一次性执行所有操作，或者更好的方法是根本不要删除它们！这是一个没有很好解释的副作用。

你可以通过使用itertools.combinations构建所有可能严格递增的序列列表，使用itertools的pairwise配方比较每对序列，然后只要至少有一个序列是严格递增的，就停止运行。

import itertools

def pairwise(iterable):
    (a, b) = itertools.tee(iterable)
    next(b, None)  # advance b
    return zip(a, b)

def almostIncreasingSequence(sequence):
    if not sequence:
        return True
        # in case of empty list
    combos = itertools.combinations(sequence, len(sequence)-1)
    # combos is each ordered combination that's missing one element
    # it is processed as an iterator, so will do no extra work if we can
    # exit early.

    def strictly_increasing(cs):
        return all(a < b for (a, b) in pairwise(cs))

    return any(strictly_increasing(c) for c in combos)

- Adam Smith

---

almostIncreasingSequence([1,2,3,2,2,2]) 返回 True，但实际上应该是 False。 - Pedro H. N. Vieira

现在已经更改了，这个算法应该可以工作（尽管它的性能要差得多）。 - Adam Smith

@JingLi 好的，第三次一定成功。 - Adam Smith

@Adam Smith，现在可以了。谢谢！我还有一个问题。是否可以更改我的原始代码，而不是删除列表中的数字？一旦sequence[i]>=sequence[j]，停止循环并将计数器加1，然后设置i=i+1？然后再次开始循环？ - M-M

如果序列为空列表（OP的代码似乎将任何长度小于3的序列算作“True”），则会出现“ValueError: r必须为非负数”。 - G_M

@DeliriousLettuce 是的，只需要特殊处理一下即可。 - Adam Smith

Answer 4

你需要做的唯一一件事就是遍历列表，计算sequence[i] > sequence[i+1]出现的次数。如果它最多出现一次，那么你的列表几乎是单调递增的。

def almostIncreasingSequence(sequence):
    count = 0
    for i in range(0, len(sequence) - 1):
        if sequence[i] > sequence[i+1]:
            count += 1
    return count < 2

你也可以避免计数，因为异常数量很少。只要找到第二个异常，就返回False，并跟踪一个布尔变量的值，该变量初始化为True。

def almostIncreasingSequence(sequence):
    increasing = True
    for i in range(0, len(sequence) - 1):
        if sequence[i] > sequence[i+1]:
            if increasing:
                increasing = False
            else:
                return False
    return True

- chepner

---

我认为这不是一个正确的算法。成对单调性不能保证整个序列的单调性。以 [5, 6, 1, 2] 为例。 - miradulo

啊，可能是我对问题的理解有所不同。 - chepner

@chepner 我犯了同样的错误，不得不重新设计我的算法。唉！ - Adam Smith