3

I have a list input:

[1, 2, 4, 3, 5, 7, 5, 3, 8, 3, 8, 5, 8, 5, 9, 5, 7, 5, 7, 4, 9, 7, 5, 7, 4, 7, 4, 7, 8, 9, 7, 5, 7, 5, 4, 9, 3, 4, 8, 4, 8, 5, 3, 5, 4, 7, 3, 7, 3, 1, 2, 7, 1, 7, 2, 1]

I need to check if the elements of a lookup_list [1,2,3,4,5,7,8,9,5,4,3,2,1] are present in the above list in a spread out manner in the same sequence.

This will illustrate what I am trying to say:

[1, 2, 4, 3, 5, 7, 5, 3, 8, 3, 8, 5, 8, 5, 9, 5, 7, 5, 7, 4, 9, 7, 5, 7, 4, 7, 4, 7, 8, 9, 7, 5, 7, 5, 4, 9, 3, 4, 8, 4, 8, 5, 3, 5, 4, 7, 3, 7, 3, 1, 2, 7, 1, 7, 2, 1]

The numbers in bold are the numbers from the lookup_list present in the same order in the input list, but with other irrelevant items in between as well.

Is there any way I can check for this?

This is the method I tried:

count = 0
a = 0
indices = []
for item in list:
    idx = -1
    if count < len(input_list):
        idx = list.index(input_list[count])
        if idx != -1:
            a = a +len(list[:idx])
            list = list[idx:]
            indices.append(a + idx)
    count = count +1
print(indices)

but it gave me the following result:

[0, 2, 5, 35, 25, 24, 33, 30, 33, 37, 38, 64, 54]

The issue is, the order of the lookup_list is not maintained in this method.

ggorlen
  • 44,755
  • 7
  • 76
  • 106
user150599
  • 49
  • 6
  • what is your question exactly? "Is there anyway I can check for this?"? – deadshot Aug 05 '20 at 05:29
  • 4
    Seems like it’s well explained: how to determine sequence equality while skipping non-common elements. That said.. this can be done with nested loops: have any work started? Just repeat the steps to solve it “by pen and paper”. How would this pen and paper algorithm be explained in words / bullet point steps? – user2864740 Aug 05 '20 at 05:31
  • Hi @deadshot, yes, user2864740 is right, I would like to know if there is any way I can check for the items from lookup_list in the input list, while skipping non relevant elements and maining the sequence order from the lookup_list. – user150599 Aug 05 '20 at 05:33
  • 1
    Can you think of a step-by-step process you would follow by hand to test for it? – Karl Knechtel Aug 05 '20 at 05:37

3 Answers3

2

You could use an iterator over your input list. Call next to get each value. If you exhaust the iterator without finding all the matches, you will get a StopIteration and then you would return False.

def check(input_, lookup_list):
    it = iter(input_)
    try:
        for i in lookup_list:
            # read values from the input list until we find one which 
            # matches the current value from the lookup list
            while next(it) != i: 
                pass
        # we found matches for everything on the lookup list
        return True
    except StopIteration:
        # we tried to go past the end of the input list
        return False
alani
  • 12,573
  • 2
  • 13
  • 23
  • 1
    List iterators support `in` as well, and `all` short-circuits, so you can reduce this to `return all(i in it for i in lookup_list)`. – chepner Feb 14 '22 at 15:53
  • @chepner Thanks. I see that this question was later marked as a duplicate of a question which has an answer to that effect - https://stackoverflow.com/a/52709319/13596037 – alani Feb 15 '22 at 10:40
1
def check_exists(l, lookup_list):
check = True
for i in lookup_list:
    try:
        index = l.index(i) 
        l = l[index+1:]
    except ValueError:
        check = False 
        break 
return check

check_exists() function will accept the complete list and lookup list as arguments and returns you True if sequence exists or false if doesn't .

Here is the full program -

def check_exists(l, lookup_list):
    check = True
    for i in lookup_list:
        try:
            index = l.index(i) 
            l = l[index+1:]
        except ValueError:
            check = False 
            break 
    return check



l = [1, 2, 4, 3, 5, 7, 5, 3, 8, 3, 8, 5, 8, 5, 9, 5, 7, 5, 7, 4, 9, 7, 5, 7, 
4, 7, 4, 7, 8, 9, 7, 5, 7, 5, 4, 9, 3, 4, 8, 4, 8, 5, 3, 5, 4, 7, 3, 7, 3, 1, 
2, 7, 1, 7, 2, 1]
lookup_list = [2,3,4,5,7,8,9,5,4,3,2,1] 

print(check_exists(l,lookup_list))
Indrajeet Singh
  • 470
  • 1
  • 6
  • 21
  • 1
    I like the idea of using `l.index` -- and what you have will clearly work -- but instead of constructing a new, shorter list each time, you could exploit the fact that `l.index` takes an optional second argument which is the starting index, and use the value of `index` saved from the previous time -- that is `index = l.index(i, index) + 1`. (Initialise `index` to 0.) – alani Aug 05 '20 at 05:57
  • It makes sense Alaniwi. I will change it. Thanks – Indrajeet Singh Aug 05 '20 at 06:12
  • 1
    @SindhuSatish brother Don't forget to update it as alaniwi commented – Indrajeet Singh Aug 08 '20 at 16:33
0

The most trivial way is to convert the first list (do not call it input!) to a string (the angle brackets keep multi digit numbers "together"):

input_str = "".join("<"+str(i)+">" for i in input_list)

Convert the second list to a regular expression that allows optional additional items between the required items:

lookup_str = ".*" + ".+".join("<"+str(i)+">" for i in lookup_list) + ".+"

Now, check if the input string matches the regular expression:

if (re.search(lookup_str, input_str)): # there is a match
DYZ
  • 55,249
  • 10
  • 64
  • 93