CODEWITHSUNDEEP
pythonarrays
user21
user21

Reputation: 249

how to determine whether it is possible to obtain a strictly increasing sequence?

I need to determine a function that for a given a sequence of integers (as an array) and that can determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.

the arrays can be in range

2 ≤ sequence.length ≤ 10^5, -10^5 ≤ sequence[i] ≤ 10^5

for example:

[1, 3, 2, 1] we can not drop any one number in order to get increasing sequence, so the function should return False. And True for [0, -2, 5, 6], [1, 1], [1, 3, 2].

I wanted to write function that deletes one number from the list and examines whether the sequence is increasing. If for all iterations we become False than the function should return False.

def almostIncreasingSequence(sequence):
    def order(A):
        n = len(A)
        for i in range(n):
           if A[i] >= A[i+1]:
              result = True
        else:
              result = False            
    for i in range(len(s0)-1):
        s_i = list(sequence)
        s_i.remove(s_i.index(s_i[i]))
           if order(s_i) == True:
    return True

But I have got a mistake:

ValueError: list.remove(x): x not in list

What is the reason? How I can finish my code?

Upvotes: 2

Views: 1071

Answers (2)

Copperfield
Copperfield

Reputation: 8510

as mentioned in the comments, you can use the numpy.diff for this, and thus avoiding the need to check every combination of removing 1 element from the list

import numpy

def almostIncreasingSequence(sequence):
    diff = numpy.diff(sequence) < 1
    return diff.sum() < 2

here first we get the difference between adjacent elements, then we ask where those differences are less than 1 and count it, and depending on the amount we get our answer.

Without numpy, we can use a similar technique 

import itertools

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a,b = itertools.tee(iterable)
    next(b,None)
    return zip(a,b) # use itertools.izip in python 2

def almostIncreasingSequence(sequence):
    return sum( a>=b for a,b in pairwise(sequence)) < 2

and this one have the advantage that use less memory than the numpy version

And here are some test for it

assert almostIncreasingSequence([0, -2, 5,  6])
assert almostIncreasingSequence([1,1])
assert almostIncreasingSequence([1,3,2])
assert almostIncreasingSequence([1,2,3,0])
assert almostIncreasingSequence([1,2,3,0,10])
assert almostIncreasingSequence([10,1,2,3,4])
assert almostIncreasingSequence([1,10,2,3,4])
assert not almostIncreasingSequence([1,2,3,0,0])
assert not almostIncreasingSequence([1,2,0,3,0,10])
assert not almostIncreasingSequence([1,2,0,3,10,0])
assert not almostIncreasingSequence([1,2,3,0,10,0])
assert not almostIncreasingSequence([10,1,2,3,10,0])
assert not almostIncreasingSequence([1, 3, 2, 1])

in response to the comments, here is an early stop version

def almostIncreasingSequence(sequence):
    diff = 0
    for a,b in pairwise(sequence):
        if a>=b:
            diff += 1
            if diff >= 2:
                return False
    return diff < 2

and an accompanying test 

assert not almostIncreasingSequence(itertools.chain([1, 3, 2, 1],range(10**100))) # use xrange with python 2

which will take ages with any of the other version

Upvotes: 3

Daniel Centore
Daniel Centore

Reputation: 3349

def almostIncreasingSequence(sequence):
    for i in range(len(sequence)-1):
        s_i = list(sequence)

        # Remove the item by index
        del s_i[i]

        if order(s_i) == True:
            return True

    # Need to return false at the end if we never find a solution
    return False

# You should have tested this function separately first.
# It did not work, so obviously almostIncreasingSequence wouldn't work.
def order(A):
    n = len(A)

    # Should have been n-1, not n, because you compare against n+1
    # which doesn't exist when you hit the tail
    for i in range(n - 1):
        if A[i] > A[i + 1]:
            # Need to actually return the value, not just set it to a variable
            return False
    # Only tell us it's in order if ALL the values don't fail
    return True

print almostIncreasingSequence([1, 3, 2])

Upvotes: 1

Related Questions