CODEWITHSUNDEEP
python
user1021090
user1021090

Reputation: 41

Comparing element order in Python lists

I am trying to write a function that returns True if the elements in lst1 appear in lst2 in the same order as they appear in lst1, but not necessarily consecutively.

For example,

test([29, 5, 100], [20, 29, 30, 50, 5, 100]) should return True.

test([25, 65, 40], [40, 25, 30, 65, 1, 100]) should return False.

Here is what I have so far:

def test(lst1, lst2):
    for i in range(len(lst1)-len(lst2)+1):
        if lst2 == lst1[i:i+len(lst2)]:
            return True 
    return False

Upvotes: 4

Views: 1078

Answers (4)

agf
agf

Reputation: 177000

Here is an iterative version of the method using index given by Triptych. I think this is probably the best way to do this, as index should be faster than any manual indexing or iteration:

def test(lst1, lst2):
    start = 0
    try:
        for item in lst1:
            start = lst2.index(item, start) + 1
    except ValueError:
        return False
    return True

It should perform much better in Python than a recursive version. It also correctly adds one to the start point after each search so as not to give false positives when there are duplicates in the first list.

Here are two solutions that iterate primarily over lst2 instead of lst1, but are otherwise similar to jedwards' version.

The first is straightforward, and uses indexing, but only indexes when you actually move to a different item in lst1, rather than for every item in lst2:

def test(lst1, lst2):
    length, i, item = len(lst1), 0, lst1[0]
    for x in lst2:
        if x == item:
            i += 1
            if i == length:
                return True
            item = lst1[i]
    return False

The second uses manual iteration over lst1 with next rather than indexing:

def test(lst1, lst2):
    it = iter(lst1)
    try:
        i = next(it)
        for x in lst2:
            if x == i:
                i = next(it)
    except StopIteration:
        return True
    return False

Both are probably slight improvements as they do less indexing and have no need to construct a range for every item in lst1.

Upvotes: 5

Kenan Banks
Kenan Banks

Reputation: 212208

Recursively, no clobbered lists, no new sublists, failing early

def find_all(needle, haystack, npos=0, hpos=0):
  if npos >= len(needle):
    return True
  try:
    return find_all(needle, haystack, npos+1, haystack.index(needle[npos], hpos)+1) 
  except ValueError:
    return False


print find_all([1,3,5], [1,2,3,4,5,6,7]) # True
print find_all([1,5,3], [1,2,3,4,5,6,7]) # False

Upvotes: 2

jedwards
jedwards

Reputation: 30260

This scans the lists and is a different approach:

def test(lst1, lst2):
    p2 = 0
    length = len(lst2)
    for e1 in lst1:
        for p in range(p2, length):
            if e1 == lst2[p]:
                p2 = p
                break
        else:
            return False    
    return True

For each element in lst1 it searches the subset of list 2 (between p2 and the end) for it. If it is found, it restricts the range following searches by updating p2. If it is not found, False is returned. True is returned if every element in lst1 is found.

Upvotes: 1

janoliver
janoliver

Reputation: 7824

def test(lst1, lst2):
    for x in lst2:
        if x == lst1[0]:
            del lst1[0]
    return lst1 == []

Should work.

Upvotes: 0

Related Questions