python - 数组中最长的蛇序列

Question

问题: 一组由空格分隔的数字作为输入传递。该程序必须打印出数字中存在的最大蛇序列。蛇序列由相邻的数字组成，因此对于每个数字，右边或左边的数字是其值的 +1 或 -1。如果可能存在多个最大长度的蛇序列，则打印以自然输入顺序出现的蛇序列。

示例输入/输出 1:

输入:

9 8 7 5 3 0 1 -2 -3 1 2

输出:

3 2 1 0 1

示例输入/输出 2:

输入:

-5 -4 -3 -1 0 1 4 6 5 4 3 4 3 2 1 0 2 -3 9

输出:

6 5 4 3 4 3 2 1 0 -1 0 1 2

示例输入/输出 3:

输入:

5 6 7 9 8 8

输出:

5 6 7 8 9 8

我在网上搜索过，只找到了在给出数字网格而不是数组时查找蛇序列的引用。

到目前为止我的解决方案:
创建一个二维数组，其中包含输入中的所有数字作为 1 个值，第二个值是可以从该数字开始生成的最大长度序列。但这并不总是生成最大长度序列，并且当有 2 条最大长度的蛇时根本不起作用。

Answer 1

假设原始数字集中的顺序无关紧要，就像您的问题中的情况一样，这似乎是 Longest Path Problem 的一个实例, 这是 NP 难的。

这样想:您可以根据数字创建一个图形，所有节点对之间的边差为 1。现在，此图中最长的简单(非循环)路径就是您的解决方案。您的第一个示例将对应于此图形和路径。 (请注意，输入集中的两个节点有两个 1 节点。)

虽然这本身并不能解决您的问题，但它应该可以帮助您开始寻找一种算法来解决(或近似)它，既然您知道该问题的更好/更常见的名称。

---

一种算法的工作原理如下:从每个数字开始，确定“相邻”数字，然后对图形进行某种深度优先搜索以确定最长路径。请记住暂时从图中删除访问过的节点。这具有 O(2ⁿ) ¹⁾ 的最坏情况复杂度，但显然对于您的示例来说已经足够了。

def longest_snake(numbers, counts, path):
    best = path
    for n in sorted(counts, key=numbers.index):
        if counts[n] > 0 and (path == [] or abs(path[-1] - n) == 1):
            counts[n] -= 1
            res = longest_snake(numbers, counts, path + [n])
            if len(res) > len(best):
                best = res
            counts[n] += 1
    return best

例子:

>>> from collections import Counter
>>> numbers = list(map(int, "9 8 7 5 3 0 1 -2 -3 1 2".split()))
>>> longest_snake(numbers, Counter(numbers), [])
[3, 2, 1, 0, 1]

请注意，此算法将可靠地找到最大的“蛇”序列，使用次数不会超过允许的次数。但是，它可能找不到预期作为输出的特定序列，即“以自然输入顺序出现的蛇序列”，无论它的意思是什么。为了更接近“自然顺序”，您可以按照输入中出现的相同顺序尝试数字(就像我对 sorted 所做的那样)，但这也不是完美的。无论如何，我相信您可以自己弄清楚其余部分。

---

¹⁾ 在这种特殊情况下，图的分支因子为 2，因此 O(2ⁿ)；在更一般的情况下，复杂度将更接近于 O(n!)。