我正在做一些信号分析,其中的一部分是寻找最长的子序列
我有如下字典:
sequenceDict = {
0: [168, 360, 470],
1: [279, 361, 471, 633, 729, 817],
2: [32, 168, 170, 350, 634, 730, 818],
3: [33, 155, 171, 363, 635, 731, 765, 819],
4: [352, 364, 732, 766, 822],
5: [157, 173, 353, 577, 637, 733, 823, 969],
6: [158, 174, 578, 638, 706, 734, 824],
7: [159, 175, 579, 707, 735],
8: [160, 464, 640, 708, 826],
9: [173, 709, 757, 827],
10: [174, 540, 642, 666, 710],
11: [253, 667, 711],
12: [254, 304, 668],
13: [181, 255, 831],
14: [256, 340, 646, 832],
16: [184, 416],
17: [417],
18: [418],
19: [875],
20: [876],
23: [217],
24: [168, 218, 880],
25: [219, 765, 881],
26: [220, 766],
27: [221],
28: [768],
29: [3, 769],
30: [344, 476, 706]}
这些基本上总是另一个数组的排序索引,我想通过从每个键中顺序地只选取一个数字(键2紧跟在键1之后,依此类推)来找到最长的递增序列(就像longest increasing subsequence),例如, 从键0和键1,[360361]是一个序列,[470471]是另一个序列。 我称之为递增序列,因为这些数字应该严格地增加1。在
我已经研究过patience sorting等等,但是由于这个问题稍有不同,而且还有一个序列树,除了从这个dict生成所有可能的序列,然后运行patience sort之外,有没有已知的python实现,或者其他有效的方法来完成这个任务?在
我只想实施一个“暴力”解决方案。。。在
Python提供
set
这可能是一个合理的选择。。。这是一个示例实现:一个棘手的部分是,如果键中有一个间隙,那么您就不能扩展序列,这就是
last_key
的用途。在复杂性应该是
O(input_size × average_number_of_sequences)
。我只是一种直觉,但我想你不能再比这低了。我很想用value - key
将一个常量与每个序列关联起来。。。然而,这不会检测到“间隙”(即键1中的值100和键3中的值102,但在键2中没有101的。在对于输入的问题,解决方案是
(7, 735, 7)
,意思是一个7元素序列,在键7处以值735结尾。在与@6502的解相比,这个解不仅保持了最佳解,而且还跟踪了每一个递增的子序列,如果这更有帮助的话。
这个想法类似于滑动窗口方法。从第一个列表开始,更新}字典,然后查看第二个列表并再次更新字典,等等
currentHotItems
和{globalHotItems
是包含结果的字典。键是(value,startIndex),value是长度。在例如,
^{pr2}$globalHotItems
中的最后4项:是:
这意味着最好的解决方案是长度7,从
index=1
列表中开始为729。最好的第二个解是长度6,从index=6
列表开始,如706,等等复杂性:
我认为复杂性应该是:
O(input_size × average_number_of_sequences)
相关问题 更多 >
编程相关推荐