Как мне найти количество упорядоченных групп, как в подсписке из суперсписка в python?

Question

Предположим, у меня есть меньший список A = [1,2,3] и больший список B = [1,2,3,1,1,2,2,3,2,3].
B не имеет других элементов, кроме A , но порядок элементов не поддерживается.

Я хочу узнать, сколько раз A появляется в B с сохранением порядка A .Для этого примера A появляется 3 раза в B .Я мог бы решить это для двух элементов, как [1,2] приходит 2 раза в [1,1,2,2,1,1].Другими словами, я хочу найти, сколько упорядоченных групп, таких A , возможно из большого списка как B .

Answer 1

Эффективный подход состоит в том, чтобы создать указание очередей индексов для каждого элемента в B, а затем циклически переключаться между элементами в A, чтобы найти следующий элемент в dict, индекс которого больше, чем индекс последнегонайти элемент путем удержания в очереди до тех пор, пока не будет найден такой индекс, или прервать цикл, если какая-либо очередь исчерпана, причем каждый завершенный цикл увеличивает счет на 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

Answer 2

Из того, что я понял, вы хотите посчитать, сколько раз все элементы A повторяются по порядку в 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