18

我正在尝试找到解决以下问题的最佳方法。通过最好的方式，我的意思是不那么复杂。

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

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

每个元素通过它的start和length表示一个序列，例如 (5,7) 等价于序列(5,6,7,8,9,10,11)- 一个以 5 开头的 7 个元素的列表。可以假设元组是按start元素排序的。

输出应返回表示最长连续序列的元组的非重叠组合。这意味着，解决方案是范围的子集，没有重叠和间隙，并且可能是最长的——尽管可能有多个。

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

[(0,5),(5,7)]相当于(0,1,2,3,4,5,6,7,8,9,10,11)

它是回溯解决这个问题的最佳方法吗？

我对人们可能提出的任何不同方法感兴趣。

此外，如果有人知道这个问题的正式参考或另一个类似的参考，我想获得参考。

顺便说一句 - 这不是家庭作业。

编辑

只是为了避免一些错误，这是另一个预期行为的例子

[(0,1),(1,7),(3,20),(8,5)]对于像正确答案这样的输入[(3,20)]等效于长度为 20 的 (3,4,5,..,22)。收到的一些答案将[(0,1),(1,7),(8,5)]等效于 (0,1,2,...,11,12)作为正确答案。但是最后一个答案是不正确的，因为它比 短[(3,20)]。

4

9 回答 9

13

使用给定的顺序（按起始元素）迭代元组列表，同时使用哈希图来跟踪以某个索引结束的最长连续序列的长度。

伪代码，跳过哈希图中未找到的项目等详细信息（如果未找到则假设返回 0）：

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) 算法。

如果您需要组成此序列的实际元组，则还需要保留一个按结束索引散列的元组链接列表，并在此端点更新最大长度时更新此列表。

更新：我对 python 的了解相当有限，但是根据您粘贴的 python 代码，我创建了返回实际序列而不是长度的代码：

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))
于 2011-01-04T16:52:49.090 回答
2

修改后的算法：

create a hashtable of start->list of tuples that start there
put all tuples in a queue of tupleSets
set the longestTupleSet to the first tuple
while the queue is not empty
    take tupleSet from the queue
    if any tuples start where the tupleSet ends
        foreach tuple that starts where the tupleSet ends
            enqueue new tupleSet of tupleSet + tuple
        continue

    if tupleSet is longer than longestTupleSet
        replace longestTupleSet with tupleSet

return longestTupleSet

c# 实现

public static IList<Pair<int, int>> FindLongestNonOverlappingRangeSet(IList<Pair<int, int>> input)
{
    var rangeStarts = input.ToLookup(x => x.First, x => x);
    var adjacentTuples = new Queue<List<Pair<int, int>>>(
        input.Select(x => new List<Pair<int, int>>
            {
                x
            }));

    var longest = new List<Pair<int, int>>
        {
            input[0]
        };
    int longestLength = input[0].Second - input[0].First;

    while (adjacentTuples.Count > 0)
    {
        var tupleSet = adjacentTuples.Dequeue();
        var last = tupleSet.Last();
        int end = last.First + last.Second;
        var sameStart = rangeStarts[end];
        if (sameStart.Any())
        {
            foreach (var nextTuple in sameStart)
            {
                adjacentTuples.Enqueue(tupleSet.Concat(new[] { nextTuple }).ToList());
            }
            continue;
        }
        int length = end - tupleSet.First().First;
        if (length > longestLength)
        {
            longestLength = length;
            longest = tupleSet;
        }
    }

    return longest;
}

测试：

[Test]
public void Given_the_first_problem_sample()
{
    var input = new[]
        {
            new Pair<int, int>(0, 5),
            new Pair<int, int>(0, 1),
            new Pair<int, int>(1, 9),
            new Pair<int, int>(5, 5),
            new Pair<int, int>(5, 7),
            new Pair<int, int>(10, 1)
        };
    var result = FindLongestNonOverlappingRangeSet(input);
    result.Count.ShouldBeEqualTo(2);
    result.First().ShouldBeSameInstanceAs(input[0]);
    result.Last().ShouldBeSameInstanceAs(input[4]);
}

[Test]
public void Given_the_second_problem_sample()
{
    var input = new[]
        {
            new Pair<int, int>(0, 1),
            new Pair<int, int>(1, 7),
            new Pair<int, int>(3, 20),
            new Pair<int, int>(8, 5)
        };
    var result = FindLongestNonOverlappingRangeSet(input);
    result.Count.ShouldBeEqualTo(1);
    result.First().ShouldBeSameInstanceAs(input[2]);
}
于 2011-01-04T15:40:31.063 回答
2

这是加权有向无环图最长路径问题的一个特例。

图中的节点是序列中最后一个元素之后的起点和点，下一个序列可以从此处开始。

这个问题很特殊，因为两个节点之间的距离必须相同，与路径无关。

于 2011-01-05T08:11:49.570 回答
1

我删除了以前的解决方案，因为它没有经过测试。

问题是在“加权有向无环图”中找到最长的路径，它可以在线性时间内解决：

http://en.wikipedia.org/wiki/Longest_path_problem#Weighted_directed_acyclic_graphs

将一组 {start position} union {(start position + end position)} 作为顶点。对于您的示例，它将是 {0, 1, 5, 10, 11, 12}

对于顶点 v0，v1，如果有一个最终值 w 使得 v0 + w =​​ v1，则添加一条连接 v0 到 v1 的有向边，并将 w 作为其权重。

现在按照维基百科页面中的伪代码。由于顶点的数量是 2xn 的最大值（n 是元组的数量），所以问题仍然可以在线性时间内解决。

于 2011-01-04T12:53:35.457 回答
1

编辑以用实际的 Python 代码替换伪代码

再次编辑以更改代码；原始算法在解决方案上，但我误解了对中的第二个值是什么！幸运的是基本算法是相同的，我能够改变它。

这是一个解决 O(N log N) 问题并且不使用哈希映射（因此没有隐藏时间）的想法。对于记忆，我们将使用 N * 2 个“事物”。

我们将为每个元组添加另外两个值：(BackCount, BackLink)。在成功的组合中，BackLink 将从最右边的元组从右到左链接到最左边的元组。BackCount 将是给定 BackLink 的值累积计数。

这是一些python代码：

def FindTuplesStartingWith(tuples, frm):
    # The Log(N) algorithm is left as an excersise for the user
    ret=[]
    for i in range(len(tuples)):
        if (tuples[i][0]==frm): ret.append(i)
    return ret

def FindLongestSequence(tuples):

    # Prepare (BackCount, BackLink) array
    bb=[] # (BackCount, BackLink)
    for OneTuple in tuples: bb.append((-1,-1))

    # Prepare
    LongestSequenceLen=-1
    LongestSequenceTail=-1

    # Algorithm
    for i in range(len(tuples)):
        if (bb[i][0] == -1): bb[i] = (0, bb[i][1])
        # Is this single pair the longest possible pair all by itself?
        if (tuples[i][1] + bb[i][0]) > LongestSequenceLen:
            LongestSequenceLen = tuples[i][1] + bb[i][0]
            LongestSequenceTail = i
        # Find next segment
        for j in FindTuplesStartingWith(tuples, tuples[i][0] + tuples[i][1]):
            if ((bb[j][0] == -1) or (bb[j][0] < (bb[i][0] + tuples[i][1]))):
                # can be linked
                bb[j] = (bb[i][0] + tuples[i][1], i)
                if ((bb[j][0] + tuples[j][1]) > LongestSequenceLen):
                    LongestSequenceLen = bb[j][0] + tuples[j][1]
                    LongestSequenceTail=j

    # Done! I'll now build up the solution
    ret=[]
    while (LongestSequenceTail > -1):
        ret.insert(0, tuples[LongestSequenceTail])
        LongestSequenceTail = bb[LongestSequenceTail][1]
    return ret

# Call the algoritm
print FindLongestSequence([(0,5), (0,1), (1,9), (5,5), (5,7), (10,1)])
>>>>>> [(0, 5), (5, 7)]
print FindLongestSequence([(0,1), (1,7), (3,20), (8,5)])    
>>>>>> [(3, 20)]

整个算法的关键是代码中“这是关键”注释的位置。我们知道我们当前的 StartTuple 可以链接到 EndTuple。如果存在一个以 EndTuple.To 结尾的较长序列，那么在我们到达这一点时就已经找到了，因为它必须从一个较小的 StartTuple.From 开始，并且数组按“From”排序！

于 2011-01-04T13:58:40.560 回答
1

这是一个简单的reduce操作。给定一对连续的元组，它们要么可以组合，要么不能组合。所以定义成对组合函数：

def combo(first,second):
    if first[0]+first[1] == second[0]:
        return [(first[0],first[1]+second[1])]
    else:
        return [first,second]

这只是返回一个组合两个参数的元素或原始两个元素的列表。

然后定义一个函数来迭代第一个列表并组合对：

def collapse(tupleList):
    first = tupleList.pop(0)
    newList = []
    for item in tupleList:
        collapsed = combo(first,item)
        if len(collapsed)==2:
            newList.append(collapsed[0])
        first = collapsed.pop()
    newList.append(first)
    return newList

这使第一个元素与列表中的当前项目（从第二个项目开始）进行比较，当它无法将它们组合起来时，它将第一个元素放入一个新列表中并替换first为两者中的第二个。

然后只需调用collapse元组列表：

>>> collapse( [(5, 7), (12, 3), (0, 5), (0, 7), (7, 2), (9, 3)] )
[(5, 10), (0, 5), (0, 12)]

[编辑] 最后，迭代结果以获得最长的序列。

def longest(seqs):
    collapsed = collapse(seqs)
    return max(collapsed, key=lambda x: x[1])

[/编辑]

复杂度 O(N)。对于奖励标记，请反向执行，以便初始pop(0)变为 apop()并且您不必重新索引数组，或者移动迭代器。对于最高分，使其作为reduce多线程优点的成对操作运行。

于 2011-01-04T14:23:40.120 回答
1

只是从基本的角度考虑算法，这行得通吗？

（为可怕的语法道歉，但我试图在这里保持语言独立）

首先是最简单的形式：找到最长的连续对。

循环遍历每个成员，并将其与其他具有更高 startpos 的成员进行比较。如果第二个成员的 startpos 等于第一个成员的 startpos 和长度之和，则它们是连续的。如果是这样，则在具有较低 startpos 和组合长度的新集合中形成一个新成员来表示这一点。

然后，将这些对中的每一对与所有具有更高 startpos 的单个成员进行比较并重复，形成一组新的连续三元组（如果存在）。

继续这个模式，直到你没有新的集合。

那么棘手的部分是您必须比较每个集合中每个成员的长度以找到真正的最长链。

我很确定这不像其他方法那样有效，但我相信这是暴力强制该解决方案的可行方法。

我很感激对此的反馈以及我可能忽略的任何错误。

于 2011-01-04T17:11:17.493 回答
0
  • 创建所有起点和终点的有序数组，并将它们全部初始化为一个
  • 对于元组中的每个项目，将结束点（开始和结束）与数组中的有序项进行比较，如果它们之间有任何点（例如，数组中的点是 5 并且开始 2 的长度为 4）将值更改为零。
  • 完成循环后，开始在有序数组中移动并在看到 1 时创建一个条带，当您看到 1 时，添加到现有条带，任意为零，关闭条带等。
  • 最后检查条带的长度

我认为复杂度在 O(4-5*N) 左右

（见更新）

N 是元组中的项目数。

更新

正如您所知道的，复杂性并不准确，但肯定非常小，因为它是线段（元组项）数量的函数。

因此，如果 N 是行数，则排序为 O(2N * log2N)。比较是 O(2N)。查找线段也是 O(2N)。所以总而言之O(2N(log2N + 2))。

于 2011-01-04T12:45:34.973 回答
0

这听起来像是一个完美的“动态规划”问题......

最简单的程序是蛮力（例如递归），但这具有指数复杂性。

使用动态编程，您可以设置长度为 n 的数组 a，其中 n 是问题的所有（开始 + 长度）值的最大值，其中 a[i] 表示最长的非重叠序列直到 a[i]。然后，您可以逐步处理所有元组，更新 a. 该算法的复杂度为 O(n*k)，其中 k 是输入值的数量。

于 2011-01-04T12:36:52.307 回答