Ad

Whats Wrong In My Subsequence Validation?

- 1 answer

I am trying to get this function to check if the list SEQUENCE is subsequence of list ARRAY. Subsequence means: must have all the numbers and they must be at the same order. In the exemple below SEQUENCE is a subsequence of ARRAY. array=[5, 1, 22, 25, 6, -1, 8, 10] sequence= [1, 6, -1, 10]

Can anyone tell me why my code doesnt work?

array=[5, 1, 22, 25, 6, -1, 8, 10] 
sequence= [1, 6, -1, 10]

def isValidSubsequence(array, sequence):
arrayValid=[]
if len(array) >= len(sequence):
    for i in range(len(sequence)):
        numSeq = sequence[i]
        for j in range(i, len(array)):
            numArr = array[j]
            if numSeq==numArr:
                arrayValid.append(numArr)
                array.remove(numArr)
            else:
                array.remove(numArr)
    if arrayValid==sequence:
        return True
    else:
        return False
else:
        return False
Ad

Answer

Your loop on j (for j in range(i, len(array)):) starts at an index that corresponds to a position in sequence. Advancing through array must be independent of the index of values in sequence.

You can do this with an iterator:

array=[5, 1, 22, 25, 6, -1, 8, 10] 
sequence= [1, 6, -1, 10]

iArray = iter(array)
isSubsequence = all(s in iArray for s in sequence)

print(isSubsequence) # True

The s in iArray part advances the iterator (iArray) up to the point where s is found. If array contains all the elements of sequence in the same order, then every s in sequence will be able to advance to a matching value in iArray.

Ad
source: stackoverflow.com
Ad