数组中的最长的蛇序列 [英] Longest Snake Sequence in an Array

问题描述

问：一组用空格分隔的数字将被作为输入传递。该程序必须打印在数字上最大的蛇序列present。蛇序列由这样的相邻号，对于每个编号，右边或左边的数字是+1或-1它的价值。如果最大长度的多个蛇序列是可能的打印出现在自然的输入顺序中的蛇顺序。

Question : A set of numbers separated by space is passed as input. The program must print the largest snake sequence present in the numbers. A snake sequence is made up of adjacent numbers such that for each number, the number on the right or left is +1 or -1 of it's value. If multiple snake sequences of maximum length is possible print the snake sequence appearing in the natural input order.

例输入/输出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

我在网上搜索和放大器;只找到引用发现时数的网格被赋予与放蛇序列;不是数组。

I have searched online & have only found references to find a snake sequence when a grid of numbers is given & not an array.

我的解决方案迄今：结果
创建一个包含所有号码从输入作为1值和第二个值是可以从这个数字开始生成最大长度序列的二维数组。但是，这并不总是产生最大长度序列，并没有当有最大长度的2蛇在所有的工作。

My Solution so far :
Create a 2D Array containing all the numbers from input as 1 value and the 2nd value being the max length sequence that can be generated starting from that number. But this doesn't always generate the max length sequence and doesn't work at all when there are 2 snakes of max length.

推荐答案

假设在原组数字的顺序并不重要，因为似乎是在你的问题的情况下，这似乎是的一个实例< A HREF =htt​​p://en.wikipedia.org/wiki/Longest_path_problem相对=nofollow>最长路径问题，这是一个NP难。

Assuming that the order in the original set of numbers does not matter, as seems to be the case in your question, this seems to be an instance of the Longest Path Problem, which is NP-hard.

想想这样的说法：你可以从你的号码创建一个图，所有的对，有一个相差节点之间的边缘。现在，最长的简单（非周期性）在该图中的路径是您的解决方案。第一个实施例将对应于该曲线图和通路。 （请注意，有两个<青霉> 1 的在输入组中的两个1节点。）

Think of it that way: You can create a graph from your numbers, with edges between all pairs of nodes that have a difference of one. Now, the longest simple (acyclic) path in this graph is your solution. Your first example would correspond to this graph and path. (Note that there are two 1 nodes for the two ones in the input set.)

虽然这本身不解决您的问题，它应该帮助你入门找到一个算法来解决（或接近）吧，现在你知道了问题的一个更好/更常见的名字。

While this in itself does not solve your problem, it should help you getting started finding an algorithm to solve (or approximate) it, now that you know a better/more common name for the problem.

一个算法是这样的：从每一个号码开始，确定了相邻的数字，并通过图形做排序的深度优先搜索，以确定的最长路径。请记住，从图中暂时删除的访问节点。这有最坏情况复杂的 O（2 ^N ）的 ^1），但显然这是足以让你的例子。

One algorithm works like this: Starting from each of the numbers, determine the "adjacent" numbers and do sort of a depth-first search through the graph to determine the longest path. Remember to temporarily remove the visited nodes from the graph. This has a worstcase complexity of O(2ⁿ) ¹⁾, but apparently it's sufficient for your examples.

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]

请注意，这种算法将可靠地发现的最大蛇的序列，不使用数字往往比允许的。然而，它可能无法找到的特定的提供预期作为输出，即，出现在自然输入顺序中的蛇序列，不管这是应该意味着序列。
为了更接近自然秩序，因为它们出现在输入你可以尝试的号码相同的顺序（如我与整理一样），但不完美，无论是。无论如何，我敢肯定，你可以自己计算出的其余部分。

Note that this algorithm will reliably find a maximum "snake" sequence, using no number more often than allowed. However, it may not find the specific sequence that's expected as the output, i.e. "the snake sequence appearing in the natural input order", whatever that's supposed to mean. To get closer to the "natural order", you might try the numbers in the same order as they appear in the input (as I did with sorted), but that does not work perfectly, either. Anyway, I'm sure you can figure out the rest by yourself.

^1）在这种特殊情况下，有图有2个分支的因素，因此O（2 ^N ）;在更一般的情况下，该复杂性将接近为O（n！）。

¹⁾ In this special case, the graph has a branching factor of 2, thus O(2ⁿ); in the more general case, the complexity would be closer to O(n!).

这篇关于数组中的最长的蛇序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！