Count list occurence in list python

Here's a generalized solution that works for subsequences of any size and for elements of any type. It's also very space-efficient, as it only operates on iterators.

from itertools import islice

def count(lst, seq):
    it = zip(*(islice(lst, i, None) for i in range(len(seq))))
    seq = tuple(seq)
    return sum(x == seq for x in it)

In [4]: count(l, (1, 2, 3))
Out[4]: 4

The idea is to create a sliding window iterator of width len(seq) over lst, and count the number of tuples equal to tuple(seq). This means that count also counts overlapping matches:

In [5]: count('aaa', 'aa')
Out[5]: 2

x = [1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5]
y = [1,2,3]

count = 0
for i in range(len(x)-len(y)):
    if x[i:i+len(y)] == y:
        count += 1
print(count)

You could iterate the list and compare sublists:

In [1]: lst = [1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5]
In [2]: sub = [1,2,3]
In [3]: [i for i, _ in enumerate(lst) if lst[i:i+len(sub)] == sub]
Out[3]: [0, 5, 10, 15]

Note, however, that on a very large list and sublist, this is pretty wasteful, as it creates very many slices of the original list to compare against the sublist. In a slightly longer version, you could use all to compare each of the relevant positions of the list with those of the sublist:

In [5]: [i for i, _ in enumerate(lst) if all(lst[i+k] == e for k, e in enumerate(sub))]
Out[5]: [0, 5, 10, 15]

This strikes me as the longest common subsequence problem repeated every time until the sequence returned is an empty list.

I think that the best that you can do in this case for an efficient algorithm is O(n*m) where n is the number of elements in your big list and m is the number of elements in your small list. You of course would have to have an extra step of removing the small sequence from the big sequence and repeating the process.

Here's the algorithm:

1. Find lcs(bigList, smallList)
2. Remove the first occurrence of the smallList from the bigList
3. Repeat until lcs is an empty list
4. Return the number of iterations

Here is an implementation of lcs that I wrote in python:

def lcs(first, second):
    results = dict()
    return lcs_mem(first, second, results)

def lcs_mem(first, second, results):
    key = ""
    if first > second:
        key = first + "," + second
    else:
        key = second + "," + first

    if len(first) == 0 or len(second) == 0:
        return ''
    elif key in results:
        return results[key]
    elif first[-1] == second[-1]:
        result = lcs(first[:-1], second[:-1]) + first[-1]
        results[key] = result
        return result
    else:
        lcsLeft = lcs(first[:-1], second)
        lcsRight = lcs(first, second[:-1])

        if len(lcsLeft) > len(lcsRight):
            return lcsLeft
        else:
            return lcsRight

def main():
    pass


if __name__ == '__main__':
    main()

Feel free to modify it to the above algorithm.

One can define the efficiency of solution from the complexity. Search more about complexity of algorithm in google.

And in your case, complexity is 2n where n is number of elements.

Here is the solution with the complexity n, cause it traverses the list only once, i.e. n number of times.

def IsSameError(x,y):
    if (len(x) != len(y)):
        return False

    i = 0
    while (i < len(y)):
        if(x[i] != y[i]):
            return False
        i += 1

    return True

x = [1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5]
y = [1, 2, 3]

xLength = len(x)
yLength = len(y)
cnt = 0
answer = []
while (cnt+3 < xLength):
    if(IsSameError([x[cnt], x[cnt+1], x[cnt+2]], y)):
        answer.append(x[cnt])
        answer.append(x[cnt+1])
        answer.append(x[cnt + 2])
        cnt = cnt + 3
    else:
        cnt = cnt + 1


print answer