How do I find the number of ordered group possible as in a sublist from a super list in python?

Suppose I have a smaller list A = [1,2,3] and larger list B = [1,2,3,1,1,2,2,3,2,3].
B has no other elements except A's but elements order is not maintained.

I want to find how many times A appears in B preserving A's order. For this example A appears 3 times in B. I could solve this for two elements, like [1,2] comes 2 times in [1,1,2,2,1,1]. In other words, I want to find how many ordered group such A is possible from the larger list as B.

728x90

2 Answers How do I find the number of ordered group possible as in a sublist from a super list in python?

From what I understood, you want to count how many times all the elements of A are repeated in order in B, even if there are other elements inbetween.

If that's the case, you can use:

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

1 months ago

An efficient approach is to build a dict of queues of indices for each item in B, then cycle through items in A to look for the next item in the dict whose index is greater than the index of the last found item by keeping dequeueing until such an index is found or break the loop if any queue is exhausted, with each completed cycle incrementing the count by 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 becomes:

3

1 months ago