算法找到最长的非重叠序列
https://stackoverflow.com/questions/4593583
-
15-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我正在尝试找到解决以下问题的最佳方法。从最佳方式来看，我的意思是不那么复杂。
作为输入，一个元组列表（开始，长度）这样：
[(0,5),(0,1),(1,9),(5,5),(5,7),(10,1)]
每个元素代表一个序列。 开始 和 长度, ，例如（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)] 相当于（3,4,5，..，22），长度为20。收到的一些答案将给出 [(0,1),(1,7),(8,5)] 相当于（0,1,2，...，11,12）作为正确的答案。但最后一个答案不正确，因为比 [(3,20)].
解决方案
使用给定的订单（通过启动元素）迭代元素列表，同时使用hashmap跟踪最长连续序列的长度 结尾 在某个索引上。
伪代码，跳过详细信息，例如在哈希图中找不到的项目（如果找不到的话，请返回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）算法。
如果您需要构成此序列的实际元组，则需要保留一个链接的元素列表，以及最终索引的Hashhs Hashh，每当更新此终点的最大长度时，都会更新此列表。
更新：我对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))
其他提示
修订算法：
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]);
}
仅考虑基本术语的算法，这会起作用吗？
（对可怕的语法表示歉意，但我试图在这里保持与语言无关）
首先是最简单的形式：找到最长的连续对。
循环浏览每个成员，并将其与其他启动pos更高的其他成员进行比较。如果第二个成员的启动POS等于启动POS的总和和第一个成员的长度，则它们是连续的。如果是这样，请在具有较低startpos的新组中形成新成员，并结合长度来表示。
然后，将这些对中的每一个进行比较，并将它们与所有单个成员进行比较，并重复较高，并形成一组新的连续三元组（如果存在）。
继续此模式，直到没有新的设置为止。
那么棘手的部分是，您必须比较每个集合的每个成员的长度，以找到真正最长的链条。
我很确定这不像其他方法那样有效，但是我相信这是一种强迫这种解决方案的可行方法。
我会感谢有关此的反馈以及我可能忽略的任何错误。
编辑以用实际的Python代码替换伪代码
再次编辑以更改代码；最初的算法是在解决方案上，但我误解了第二个配对中的第二个价值！ Fortunatelly基本算法是相同的，我能够更改它。
这是一个解决o（n log n）中问题并且不使用哈希地图（因此没有隐藏时间）的想法。为了记忆，我们将使用n * 2“事物”。
我们将在每个元组中添加两个值：（背面，反向链接）。在成功的组合组合中，反向链接将从右至左链接到最左侧的元组链接到最左侧的元组。背面将是给定反向链接的值累计计数。
这是一些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处结束的较长序列存在，则可以在我们到达这一点的时候发现，因为它必须从较小的starttuple.trom开始，并且该数组被“从”！
我删除了先前的解决方案，因为它没有进行测试。
问题是在“加权定向无环图”中找到最长的路径，可以在线性时间内解决：
http://en.wikipedia.org/wiki/longest_path_problem#weighted_directed_acyclic_graphs
将一组{启动位置}联合{（启动位置 +端位置）}作为顶点。对于您的示例，它将是{0、1、5、10、11、12}
对于顶点v0，v1，如果有一个端值w可以使V0 + W = V1，则将将V0连接到V1的有向边缘添加并将W作为其重量。
现在按照Wikipedia页面中的伪代码。由于顶点的数量是2xN的最大值（n为元组的n），因此问题仍然可以在线性时间内解决。
这是一个简单的减少操作。给定一对连续的元组，它们可以或不能合并。因此定义成对组合函数：
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) 变成一个 pop() 而且您不必重新索引数组，也不必移动迭代器。对于顶部标记，它使其成对运行 reduce 多线程优点的操作。
这听起来像是一个完美的“动态编程”问题...
最简单的程序是做蛮力（例如递归），但这具有指数的复杂性。
通过动态编程，您可以设置一个长度为n的数组A，其中n是问题的所有（开始+长度）值的最大值，其中a [i]表示最长的非重叠顺序为[i]。然后，您可以踩所有元素，更新A。该算法的复杂性为O（n*k），其中k是输入值的数量。
- 创建一个有序的所有起点和终点，并初始化所有这些数组
- 对于元组中的每个项目，将终点（启动和结尾）与数组中的有序项目进行比较，如果它们之间有任何点（例如，数组中的点为5，并且您的启动时间为2，则长度为4）将值更改为零。
- 完成循环后，开始在订购的阵列上移动并在看到1时创建条带，然后看到1时，添加到现有条带中，并以任何零，关闭条带，然后将其添加。
- 最后检查条的长度
我认为复杂性是 在O（4-5*n）附近
（请参阅更新）
n是元组中的物品数量。
更新
正如您发现的那样，复杂性不是准确的，但绝对很小，因为它是线路伸展数量（元组项目）的函数。
因此，如果n是线伸展的数量，则排序为o（2n * log2n）。比较是O（2n）。查找线拉伸也是O（2n）。总的来说 o（2n（log2n + 2））.
