计算一个序列中子序列的数量，其间有最大允许事件

Question

给定一个主要事件序列（例如，A->B->A->B->B）、一个子序列（A->B）和中间允许的最大事件数（n），我想计算主序列中子序列的数量（N）。

例如，

N=2 for n=0（第一个 A -> 第一个 B，第二个 A -> 第二个 B）

N=3 for n=1（第一个 A -> 第一个 B，第二个 A -> 第二个 B，第二个 A -> 第三个 B）

N=4 for n=2（第一个 A -> 第一个 B，第二个 A -> 第二个 B，第二个 A -> 第三个 B，第一个 A -> 第二个 B）

N=5 for n=3 (第一个A -> 第一个B，第二个A -> 第二个B，第二个A -> 第三个B，第一个A -> 第二个B，第一个A -> 第三个B)

这个问题有有效的算法吗？我的问题的主序列可能很长，我有很多子序列需要计算。

Answer 1

您可能会使用正则表达式得到一些结果，但这取决于您的事件定义的复杂程度。或者你可以选择

result = [(first,first+steps+1)
          for steps in range(len(seq)-1) for first in range(len(seq)-steps-1)
          if seq[first]==target[0] and seq[first+steps+1]==target[1]]

>>> result
[(0, 1), (2, 3), (2, 4), (0, 3), (0, 4)]

虽然我不知道它对大型数据集是否足够有效

计算一个序列中子序列的数量，其间有最大允许事件

Count number of subsequences within a sequence with max allowed events in between

python

algorithm

sequence