算法找到最长非重叠序列 [英] algorithm to find longest non-overlapping sequences

问题描述

我试图找出解决下列问题的最佳途径。通过最好的方式，我的意思是不那么复杂。

I am trying to find the best way to solve the following problem. By best way I mean less complex.

作为输入的元组（开始，长度）这样的列表：

As an input a list of tuples (start,length) such:

[(0,5),(0,1),(1,9),(5,5),(5,7),(10,1)]

再$ P $的每个元素的pset序列由它的启动和长度的，例如（5,7）相当于序列 （5,6,7,8,9,10,11） - 从5一7个元素的列表可以假定元组是由启动排序元素。

Each element represets a sequence by its start and length, for example (5,7) is equivalent to the sequence (5,6,7,8,9,10,11) - a list of 7 elements starting with 5. One can assume that the tuples are sorted by the start element.

应返回重新present最长连续序列（多个）元组的非重叠组合的输出。这意味着，一个解决方案是，没有重叠和没有间隙的范围的子集，是可能的最长的 - 有可能虽然多于一个。

The output should return a non-overlapping combination of tuples that represent the longest continuous sequences(s). This means that, a solution is a subset of ranges with no overlaps and no gaps and is the longest possible - there could be more than one though.

例如对于给定输入的解决方案是：

For example for the given input the solution is:

[（0,5），（5,7）] 等同于（0,1,2,3,4,5， 6,7,8,9,10,11）

时，它回溯最好的办法来解决这个问题呢？

is it backtracking the best approach to solve this problem ?

我感兴趣的任何不同的方法，人们可以建议。

I'm interested in any different approaches that people could suggest.

此外，如果任何人都知道这个问题，或者另外一个类似的正式参考我想获得引用。

Also if anyone knows a formal reference of this problem or another one that is similar I'd like to get references.

顺便说一句 - 这不是功课。

BTW - this is not homework.

修改

只是为了避免一些错误，这是正常现象的另一个例子

Just to avoid some mistakes this is another example of expected behaviour

对于像输入[（0,1），（1,7），（3,20），（8,5）] 的正确答案是 [（3,20）] 等同于（3,4,5，...，22），长度20.一些收到会给出答案的 [（0,1），（1,7），（8,5）] 等价于（0,1,2，...，11,12），为正确的答案。但是，这最后的答案是不正确的，因为是短于 [（3,20）] 。

for an input like [(0,1),(1,7),(3,20),(8,5)] the right answer is [(3,20)] equivalent to (3,4,5,..,22) with length 20. Some of the answers received would give [(0,1),(1,7),(8,5)] equivalent to (0,1,2,...,11,12) as right answer. But this last answer is not correct because is shorter than [(3,20)].

推荐答案

迭代使用给定顺序（由起始元素），而使用一个HashMap来跟踪时间最长的连续序列的长度的元组的列表中的结束的在一定的指数。

Iterate over the list of tuples using the given ordering (by start element), while using a hashmap to keep track of the length of the longest continuous sequence ending on a certain index.

伪code，跳绳就像一个HashMap中没有发现项目的详细信息（假设返回0，如果没有找到）：

pseudo-code, skipping details like items not found in a hashmap (assume 0 returned if not found):

int bestEnd = 0;
hashmap<int,int> seq // seq[key] = length of the longest sequence ending on key-1, or 0 if not found
foreach (tuple in orderedTuples) {
    int seqLength = seq[tuple.start] + tuple.length
    int tupleEnd = tuple.start+tuple.length;
    seq[tupleEnd] = max(seq[tupleEnd], seqLength)
    if (seqLength > seq[bestEnd]) bestEnd = tupleEnd
}
return new tuple(bestEnd-seq[bestEnd], seq[bestEnd])

这是一个O（n）的算法。

This is an O(N) algorithm.

如果您需要实际的元组制作了这个序列，你需要不断的元组最终指数散列以及链表，该更新的时候最大长度为这个终点更新。

If you need the actual tuples making up this sequence, you'd need to keep a linked list of tuples hashed by end index as well, updating this whenever the max length is updated for this end-point.

更新：我的蟒蛇知识是相当有限的，但基于Python code您粘贴，我创造了这个code，返回的实际序列，而不只是长度：

UPDATE: My knowledge of python is rather limited, but based on the python code you pasted, I created this code that returns the actual sequence instead of just the length:

def get_longest(arr):
    bestEnd = 0;
    seqLengths = dict() #seqLengths[key] = length of the longest sequence ending on key-1, or 0 if not found
    seqTuples = dict() #seqTuples[key] = the last tuple used in this longest sequence
    for t in arr:
        seqLength = seqLengths.get(t[0],0) + t[1]
        tupleEnd = t[0] + t[1]
        if (seqLength > seqLengths.get(tupleEnd,0)):
            seqLengths[tupleEnd] = seqLength
            seqTuples[tupleEnd] = t
            if seqLength > seqLengths.get(bestEnd,0):
                bestEnd = tupleEnd
    longestSeq = []
    while (bestEnd in seqTuples):
        longestSeq.append(seqTuples[bestEnd])
        bestEnd -= seqTuples[bestEnd][1]
    longestSeq.reverse()
    return longestSeq


if __name__ == "__main__":
    a = [(0,3),(1,4),(1,1),(1,8),(5,2),(5,5),(5,6),(10,2)]
    print(get_longest(a))

这篇关于算法找到最长非重叠序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！