python – 在列表中查找特定的子列表

发布时间：2020-12-20 12:06:47 所属栏目：Python 来源：网络整理

导读：假设我们有以下列表： sequence = ['2','4','1','2','3','4']#indices 0 1 2 3 4 5 6 7 8 9 10 接下来,我们有以下列表： key_list = ['2','4'] 现在,我想从序列中提取所有可能的子列表,这些子列表保留了密钥列表的顺序,即其索引. 让我举例说明.因此,对于序列

假设我们有以下列表：

sequence = ['2','4','1','2','3','4']
#indices     0    1    2    3    4    5    6    7    8    9    10

接下来,我们有以下列表：

key_list = ['2','4']

现在,我想从序列中提取所有可能的子列表,这些子列表保留了密钥列表的顺序,即其索引.

让我举例说明.因此,对于序列,保留key_list顺序的所有可能的索引子列表是：

[0,3,5]
[0,7]
[0,9]
[0,10]

[0,6,8,10]

[3,7]
[3,9]
[3,10]

[6,9]
[6,10]

有什么建议？

编辑：我正在使用一个大数据集,我必须为文件的每一行执行此操作,所以我正在寻找一种非常优化的方法来做到这一点,通过避免蛮力方法(制作所有可能的序列组合)

附：我不知道问题的标题是否合适,如果您有更好的标题,请随时更改.

解决方法

它可能需要一些优化,也许比列表列表更好的结构,以避免我现在正在做的愚蠢的复制和插入,但我认为这应该在最糟糕的复杂性len(序列)^ 2(不确定)关于复杂性).

sequence = ['2','4']
key_list = ['2','4']

sub_lists = []
final_sub_lists = set()
len_key_list = len(key_list)

for index,value in enumerate(sequence):
    for sub_list in sub_lists:
        len_sub_list = len(sub_list)
        # Test if current value can continue the current sub list
        if len_sub_list < len_key_list and key_list[len_sub_list] == value:
            if len_sub_list == len_key_list - 1:
                # We have found a complete sub list
                final_sub_lists.add(tuple(sub_list + [index]))
            else:
                # We copy the current sub list to be sure not miss any sub lists
                # like for instance (6,9) and (6,10).
                sub_lists.insert(0,sub_list[:])
                sub_list.append(index)
    if key_list[0] == value:
        # Start a new sub list
        sub_lists.append([index])

print sorted(final_sub_lists)

说明：sub_lists是包含到目前为止匹配的索引的列表列表.当sub_list匹配key_list的所有值时,它将附加到set final_sub_lists.

它没有经过全面测试,所以请随意纠正或指出优化！

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!