假设我们有以下列表:
sequence = ['2', '4', '1', '2', '3', '4', '2', '4', '2', '4', '4']
#indices 0 1 2 3 4 5 6 7 8 9 10
接下来，我们有以下列表:
key_list = ['2', '2', '4']
现在，我想从sequence中提取所有可能的子列表，这些子列表保持keylist的顺序，即它的索引。
让我举例说明。因此，对于sequence，保持key_list顺序的所有可能的索引子表为:
[0, 3, 5]
[0, 3, 7]
[0, 3, 9]
[0, 3, 10]
[0, 6, 7]
[0, 6, 9]
[0, 6, 10]
[0, 8, 9]
[0, 8, 10]
[3, 6, 7]
[3, 6, 9]
[3, 6, 10]
[3, 8, 9]
[3, 8, 10]
[6, 8, 9]
[6, 8, 10]
有什么建议吗?
编辑:我正在使用一个大数据集，我必须为文件的每一行执行此操作，所以我正在寻找一种非常优化的方法来做到这一点，通过避免暴力方法(使序列的所有可能组合)
注:我不知道问题的标题是否合适，如果你有更好的，请随意更改。
您可以使用itertools.combinations。在enumerate(sequence)(与r=len(key_list))上应用combinations()以从列表中获得所有r长度组合，并且由于enumerate()返回索引和项，我们可以轻松地在这里获得索引:
>>> from itertools import combinations
>>> for c in combinations(enumerate(sequence), len(key_list)):
indices, data = zip(*c)
if list(data) == key_list:
print indices
...
(0, 3, 5)
(0, 3, 7)
(0, 3, 9)
(0, 3, 10)
(0, 6, 7)
(0, 6, 9)
(0, 6, 10)
(0, 8, 9)
(0, 8, 10)
(3, 6, 7)
(3, 6, 9)
(3, 6, 10)
(3, 8, 9)
(3, 8, 10)
(6, 8, 9)
(6, 8, 10)
它可能需要一些优化，也许比列表的列表更好的结构，以避免愚蠢的复制和插入，我现在正在做的，但我认为这应该做最坏的复杂性len(sequence)^2的技巧(不确定的复杂性虽然)。
sequence = ['2', '4', '1', '2', '3', '4', '2', '4', '2', '4', '4']
key_list = ['2', '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, 8, 9) and (6, 8, 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的所有值时，它被附加到final_sub_lists集合。
它没有完全测试过，所以请随意纠正或指出优化!
这是一个递归的方法。
查找第一个键的每个索引。然后我使用相同的函数来查找以下键并连接所有索引…
def indexLists(sequence, key_list, seq_start=0, key_start=0):
"""
seq_start - where I start looking up in sequence
key_start - which key I am looking up: key = key_list[key_start]
"""
keyIndexes = []
# I look up all indices of key_list[key_start] that are higher than seq_start
while True:
try:
keyIndexes.append(
sequence.index(
key_list[key_start],# what I want to look up
keyIndexes[-1]+1 if keyIndexes else seq_start # starting after the last entry or seq_start
)
)
except:
break # if there is an error, the are no more indices
# if there are more entries in key_list
if key_start+1 < len(key_list):
# I look up the possible indexes of the following key(s) and combine them
return [(keyIndex,)+nextKeys for keyIndex in keyIndexes for nextKeys in indexLists(sequence, key_list, keyIndex+1, key_start+1)]
else:
# for the last key in key_list i just return all possible keyIndexes as 1-tuples
return [(keyIndex, ) for keyIndex in keyIndexes]
例子:
sequence = ['2', '4', '1', '2', '3', '4', '2', '4', '2', '4', '4']
key_list = ['2', '2', '4']
indexLists(sequence, key_list)
Out[37]:
[(0, 3, 5),
(0, 3, 7),
(0, 3, 9),
(0, 3, 10),
(0, 6, 7),
(0, 6, 9),
(0, 6, 10),
(0, 8, 9),
(0, 8, 10),
(3, 6, 7),
(3, 6, 9),
(3, 6, 10),
(3, 8, 9),
(3, 8, 10),
(6, 8, 9),
(6, 8, 10)]
这扩展了Sebastiens的答案，认识到你不需要任何不在key_list(现在是key_tuple)中的序列成员，只要你保留剩下的原始索引:
>>> from itertools import combinations
>>> sequence = ['2', '4', '1', '2', '3', '4', '2', '4', '2', '4', '4']
>>> key_tuple = ('2', '2', '4')
>>> keys = set(key_tuple)
>>> seq = [(indx, val) for indx, val in enumerate(sequence) if val in keys]
>>> seq
[(0, '2'), (1, '4'), (3, '2'), (5, '4'), (6, '2'), (7, '4'), (8, '2'), (9, '4'), (10, '4')]
>>> answer = []
>>> for c in combinations(seq, len(key_tuple)):
... indxs, vals = zip(*c)
... if vals == key_tuple:
... answer.append(indxs)
...
>>> answer
[(0, 3, 5), (0, 3, 7), (0, 3, 9), (0, 3, 10), (0, 6, 7), (0, 6, 9), (0, 6, 10), (0, 8, 9), (0, 8, 10), (3, 6, 7), (3, 6, 9), (3, 6, 10), (3, 8, 9), (3, 8, 10), (6, 8, 9), (6, 8, 10)]
>>>
这是一个简单的最长公共子序列问题。与通常表述的唯一不同之处在于，您想要的是位置，而不是字符本身，并且您假设key_list序列作为sequence的子序列整体出现，而LCS问题没有做这个假设。
LCS问题与两个序列(例如DNA序列)的最优对齐问题密切相关，可以使用Needleman-Wunsch动态规划算法在O(n^2)时间内解决，但只能给出一个解;在最坏的情况下，枚举所有这些元素可能会花费指数级长的时间(考虑在2k个1的列表中查找k个1的列表以查找较大的k;有(2k选k)个答案。也就是说，从DP矩阵中获取位置就像获取字符一样容易，枚举所有解决方案而不是单个解决方案也很简单:当您回溯DP矩阵时，每当您遇到两个或所有三个内边具有(相等)最大值的单元格时(而不是只有一个内边是唯一最大值)，递归处理所有它们，而不是选择任意一个。
顺便说一下，如果key_list在sequence中没有作为子序列出现，那么LCS算法将找到所有"最接近"匹配的位置——那些缺失字符最少的位置。这可能对你有用，也可能没用。
我的第二个答案找到序列中所有键的索引一次，然后使用递归迭代器(Python 2.x/3. x)。所以我没有使用yield from，找到可能的索引组合:
from collections import defaultdict
sequence = ['2', '4', '1', '2', '3', '4', '2', '4', '2', '4', '4']
key_list = ['2', '2', '4']
keys = set(key_list)
key_indices = defaultdict(list)
for indx, val in enumerate(sequence):
if val in keys:
key_indices[val].append(indx)
print('key_indices =', key_indices)
def expander(keysleft, indices, sofar=None):
#print(' keysleft, sofar =', keysleft, sofar )
if sofar is None :
sofar = []
if sofar == []:
indxleft = -1
else:
indxleft = sofar[-1]
if keysleft:
keyval, keyrest = keysleft[0], keysleft[1:]
for keyindx in indices[keyval]:
if keyindx > indxleft:
if not keyrest:
# No more to do so
yield tuple(sofar + [keyindx])
else:
for x in expander(keyrest, indices, sofar + [keyindx]):
yield x
ans = list(expander(key_list, dict(key_indices)))
print(ans)
key_indices = defaultdict(<class 'list'>, {'4': [1, 5, 7, 9, 10], '2': [0, 3, 6, 8]})
[(0, 3, 5), (0, 3, 7), (0, 3, 9), (0, 3, 10), (0, 6, 7), (0, 6, 9), (0, 6, 10), (0, 8, 9), (0, 8, 10), (3, 6, 7), (3, 6, 9), (3, 6, 10), (3, 8, 9), (3, 8, 10), (6, 8, 9), (6, 8, 10)]