如何找到一组有序的可能的数量从Python中的超级列表中的子表？

Question

假设我有一个小名单A = [1,2,3]和更大的列表B = [1,2,3,1,1,2,2,3,2,3]。 B有一个除外的任何其他元素，但元素顺序是不维护。

我想找到一个出现了多少次B中保留A的顺序。对于此示例A出现在B. 3次我可以解决这个两个元素，如[1,2]自带2倍[1,1,2,2,1,1]。换句话说，我想找到多少组有序这种可能从较大的列表为B.

Answer 1

从我的理解，你要计算多少次的所有元素都被重复，才能在B，即使有其他元素其间。

如果是这样的话，你可以使用：

A = [1,2,3]

B = [1,1,1,1,1,1,1,1,1,2,3,1,1,2,2,3,2,3,3,3,3,3,3,3,3]

counters = [0 for _ in A] # initialize a list with the same number of values of A, but all at 0


for x in B: # for each element in B
    for n in range(len(A)): # for all the indexes in A
        if x == A[n]: # if the element in B is present in A
            if n == 0 or (counters[n] < counters[n-1]):
            # if n == 0, is the first element of A: we know it's a start of a possible match
            # if the previous number in index is higher of the current number, means that we are looking for the match to continue
                counters[n] += 1 # add 1 to the current number
                break

print counters[-1] # the last number of the counters represent the times that you reached the end of a match

Answer 2

一个有效的方法是建立索引的队列的字典中B各项目，然后通过A项目来寻找其索引大于最后找到的项目在指数大于通过保持出队，直到该字典的下一个项目周期索引被发现或中断环路如果任何队列耗尽时，与每个完成的循环递增1计数：

from collections import deque
index = {}
for i, n in enumerate(B):
    index.setdefault(n, deque()).append(i)
count = 0
while True:
    last = -1
    try:
        for n in A:
            while True:
                i = index[n].popleft()
                if i > last:
                    last = i
                    break
    except (IndexError, KeyError):
        break
    count += 1

count变为：

3