How to solve the duplicate integer issue in an array for the isValidSubsequence(array, sequence) que-CodePudding

prompt for isValidSubsequence

def isValidSubsequence(array, sequence):
    index = -1
    # issue is with initialising the index variable 
    if len(sequence)<=len(array):
        for i in range(len(sequence)):
        # i refers to the i in the sequence 
            if sequence[i] in array:
                # causing a problem for repetitions such as array = [1,1,1,1,1] and subsequence = [1,1,1]
                # array.index(sequence[i]) would call the first 1 instead of the second 1 
                if array.index(sequence[i]) > index:
                    index = array.index(sequence[i])
                else:
                    return False
            else:
                return False 
        return True
    else:
        return False

How to solve this repeating 1s issue using my code?

CodePudding user response：

The reason array.index(sequence[i]) calls the first 1 is because sequence[i] is 1 in your case, and that is the same as if you called array.index(1). The index function searches your array for 1 and as soon as it finds it, it returns its index, so it always finds the first 1 first and then stops looking and returns its index.

Try something like this, this should work:

def isValidSubsequence(array, sequence):
lastIndex = -1
if not len(array) >= len(sequence):
    return False

for i in range(len(sequence)):
    containsInt = False
    for j in range(lastIndex   1, len(array)):
        if array[j] == sequence[i]:
            containsInt = True
            lastIndex = j
            break
    if not containsInt:
        return False
return True

CodePudding user response：

You are using lists, not arrays. list.index(x[, start[, end]]) can take positionals from where to where search - you could rewrite your algo to remember the last found position for each value and look for new values from that position.

BUT: this is irrelevant, you only need to concern yourself with how many of each element are in original and sequence and if one has at most equal of them...

The correct way to solve this ist to count the occurences of elements in the original, subtract the amount of occurences in the `sequence`` and evaluate your numbers:

If sequence is empty, contains elements not in original or contains more elements then inside original it can not be a subsequence:

from collections import Counter

def isValidSubsequence(array, sequence):
    # check empty sequence
    if not sequence:
        return False

    original = Counter(array)

    # check any in seq that is not in original
    if any(i not in original for i in sequence):
        return False

    # remove number of occurences in sequence from originals
    original.subtract(sequence)

    # check if too many of them in sequence
    if any(v < 0 for v in original.values()):
        return False

    return True

Testcode:

source = [1,2,3,4]
test_cases = [[1], [2,4], [1,2,4] ]
neg_test_case = [[2,5], [9], []]

for tc in test_cases:
    print(isValidSubsequence(source,tc), "should be True")

for ntc in neg_test_case:
    print(isValidSubsequence(source,ntc), "should be False")

Output:

True should be True  
True should be True  
True should be True  
False should be False
False should be False
False should be False

If you are not allowed to import, count yourself (expand this yourself):

# not efficient
counted = {d:original.count(d) for d in frozenset(original)}

# remove numbers
for d in sequence:
    counted.setdefault(d,0)
    counted[d] -= 1