python - 在列表列表中查找最长递增子序列的最有效方法

Question

我正在做一些信号分析，其中一部分是寻找最长的子序列

我有如下字典:

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]}

这些基本上总是另一个数组的排序索引，我想找到最长的递增序列(就像 longest increasing subsequence )，方法是从每个键中按顺序只选择一个数字(键 2 紧跟在键 1 之后，所以上)，例如，从键 0 和 1 开始，[360, 361] 是一个序列，[470, 471] 是另一个序列。我称这些为递增序列，因为这些数字应该严格增加 1。

我看过类似 patience sorting 的东西等等，但由于这个问题略有不同，并且还有一个序列树，是否有任何已知的 python 实现或其他有效的方法来执行此操作，除了从这个字典生成所有可能的序列然后运行耐心排序？

Answer 1

我只想实现“蛮力”解决方案...

1. 保留一个“当前序列”列表，最初是空的
2. 对于每个键，检查当前序列中的任何一个是否可以扩展一个步骤。增加序列更新也是迄今为止最好的解决方案。
3. 对于任何未用于扩展序列的数字，开始一个长度为 1 的新序列

Python 提供的 set 可能是一个合理的选择……这是一个示例实现:

best = None
current_sequences = set()
last_key = None
for key in sorted(sequenceDict.keys()):
    data = set(sequenceDict[key])
    new_sequences = set()
    if last_key == key-1:
        # no gap in key value, may be some sequence got extended
        for val, count in current_sequences:
            if val+1 in data:
                # found a continuation, keep this sequence
                new_sequences.add((val+1, count+1))
                data.remove(val+1)
                if best is None or count+1 > best[0]:
                    # we've got a new champion
                    best = count+1, val+1, key
    # add new sequences starting here
    for v in data:
        new_sequences.add((v, 1))
        if best is None:
            best = 1, v, key
    current_sequences = new_sequences
    last_key = key

一个棘手的部分是，如果键中存在间隙，则无法扩展序列，这就是 last_key 的用途。

复杂度应该是O(input_size × average_number_of_sequences)。我的只是一种直觉，但我的猜测是你不能再低了。我被使用 value - key 将一个常量值与每个序列相关联的想法所吸引......但是这不会检测到“差距”(即键 1 中的值 100 和键 3 中的值 102 , 但 没有 键 2 中的 101).

随着问题的输入，解决方案是 (7, 735, 7)，这意味着一个 7 元素序列在键 7 处以值 735 结尾。