How to check whether it is possible to obtain an increasing list by deleting one of its element in python?

Question

what i want to do(python language):

I want to check whether it is possible to obtain a list by deleting one of its element such that the list is in increasing order .

e.g: for list = [1,2,4,3], it is POSSIBLE to obtain a list that is in increasing order by removing 4 .

. is there any way such that i can remove 1 number (temporary) and check whether:

sorted(list) == list

e.g: list = [1,2,4,3]

.1st i want to remove 1 and then check with [2,4,3]

.then i want to remove only 2 from list and check with list [1,4,3] and so on ..

How can i do that in python;

What about: `>>> lst = [1,2,4,3] >>> del lst[2] >>> lst == sorted(lst) True` ? — Vinícius Figueiredo, Jul 16 '17 at 06:02
@ViníciusAguiar That's hard coded. OP probably wants something that can be used for all numeric lists. — Zizouz212, Jul 16 '17 at 06:04
@ViníciusAguiar The problem with that is that we don't always know for sure that the item at the second index is the one that needs to be removed. — Christian Dean, Jul 16 '17 at 06:04
@ChristianDean Oh, I see, I misinterpreted the question then, thanks! — Vinícius Figueiredo, Jul 16 '17 at 06:05

Denis Kuzin · Answer 1 · 2017-07-16T11:10:57.417

O(n) algorithm:

def almostSorted(L):
    """ function to check whether it is possible to obtain 
        a list by deleting one of its element such that 
        the list is in increasing order"""

    #uncomment the below line if you want to remain original list 
    #(in this case, func almostSorted(L) will work with copy of L) 
    #L = L[:]

    lenL = len(L)
    if lenL <= 2 :
        return True

    counter = 0
    while L[0] > L[1] and lenL != 1:
        del L[0]
        counter, lenL = counter+1, lenL-1

    i = 0
    while i+1 < lenL:
        if L[i+1] >= L[i]:
            i = i+1
            continue

        counter += 1

        if L[i+1] >= L[i-1]:
            del L[i]
        elif L[i+1] < L[i-1]:
            del L[i+1]
        lenL -= 1

    if counter > 1:
        return False
    else:
        return True

Test 1:

L = [1,2,3,4,5]
print L
print almostSorted(L)
print L

[1, 2, 3, 4, 5]
True
[1, 2, 3, 4, 5]

Test 2:

L = [10,2,3,4,5]
print L
print almostSorted(L)
print L

[10, 2, 3, 4, 5]
True
[2, 3, 4, 5]

Test 3:

L = [1,2,3,4,1]
print L
print almostSorted(L)
print L

[1, 2, 3, 4, 1]
True
[1, 2, 3, 4]

score 2 · Answer 2 · answered Jul 16 '17 at 06:13

2

Just do like this:

def check(lst):
    if len(lst) < 2:
        return False
    for i in range(len(lst)):
        new_lst = lst[:i] + lst[i+1:]
        if sorted(new_lst) == new_lst:
            return True
    return False

if __name__ == '__main__':
    print(check([1, 2, 4, 3])) # True
    print(check([1, 2, 4, 3, 2])) # False

answered Jul 16 '17 at 06:13

williezh

917
5
8

what does `if __name__ == '__main__' `mean – Hissaan Ali Jul 16 '17 at 09:17
1

@SyedHissaan Come on, this at least can be googled easily: https://stackoverflow.com/questions/419163/what-does-if-name-main-do. – Gassa Jul 16 '17 at 10:10
complexity is `O(n^2)`, the algorithm is very slow for large n – Denis Kuzin Jul 16 '17 at 11:14
1

Should'nt you return `True` if `len(lst) < 2` ? – hivert Jul 16 '17 at 12:34
@hivert I think raise a Exception may be better. – williezh Jul 16 '17 at 13:08

score 1 · Answer 3 · answered Jul 16 '17 at 06:03

1

You will have to create a copy of the list before doing del list[x] on any index. Lists are mutable and hence you will lose the original list once you delete any element from it.

You would need the original list to check all permutations.

answered Jul 16 '17 at 06:03

Afaq

1,146
1
13
25

score 1 · Answer 4 · answered Jul 16 '17 at 06:03

1

Just loop through the list and try removing every element.

import copy

def is_increasing(sequence):
    sequence_n = copy.copy(sequence)
    for element in sequence:
        sequence_n.remove(element)
        if sorted(sequence_n) == sequence:
            return True
        sequence_n = copy.copy(sequence)
    return False

answered Jul 16 '17 at 06:03

Zizouz212

4,908
5
42
66

1

`sorted(sequence_n) == sequence` is always false. – darksky Jul 16 '17 at 06:15

How to check whether it is possible to obtain an increasing list by deleting one of its element in python?

4 Answers4