Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Return the index of the first element in the list from where incremental increase starts

Suppose I have a list like this, where numbers increase in different steps:

[ 0,  4,  6,  8, 12, 15, 19, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]

I want to return the index for the first element in the list where the increase is incremental (+1 step only). In this case, 23 is the first location from which point the increase becomes incremental, and its index would be 8, which is what I want as an output.

What would be an elegant simple way to achieve this? This is what I have tried:

>>> for (a,b) in zip(l, l[1:]):
...     if b-a == 1:
...             print(l.index(a))
...             break

UPDATE: In this particular setup, once the increase becomes incremental it will continue to stay that way. It is possible that the increase will never become incremental.

like image 731
Clement Attlee Avatar asked Mar 02 '23 09:03

Clement Attlee


2 Answers

Solution 1: operator

from operator import sub, indexOf

L = [ 0,  4,  6,  8, 12, 15, 19, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]

print(indexOf(map(sub, L[1:], L), 1))
# prints 8

Raises ValueError: sequence.index(x): x not in sequence if difference 1 never occurs, so might want to use try/except for that.

Solution 2: bisect

This one only takes O(log n) time, using the monotonicity of incrementalness (as you commented "once the increase becomes incremental it will continue to stay that way").

from bisect import bisect

L = [ 0,  4,  6,  8, 12, 15, 19, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]

class IsIncremental:
    def __getitem__(_, i):
        return L[i+1] - L[i] == 1

print(bisect(IsIncremental(), False, 0, len(L) - 1))
# prints 8

Prints len(L) - 1 if difference 1 never occurs.

Btw... readability

As PEP 8 says:

Never use the characters 'l' (lowercase letter el), [...] as single character variable names. In some fonts, these characters are indistinguishable from the numerals one and zero. When tempted to use 'l', use 'L' instead.

like image 172
Kelly Bundy Avatar answered Apr 20 '23 00:04

Kelly Bundy


Steps:

  1. Iterate over the array until the second last element.
  2. Check if next element value differs from current element value by exactly 1.
  3. Print the index and break the loop.

Code:

my_list = [0, 4, 6, 8, 12, 15, 19, 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]
for i in range(len(my_list)-1):
    if my_list[i+1] - my_list[i] == 1:
        print(i)
        break

Result:

8

like image 41
holydragon Avatar answered Apr 20 '23 00:04

holydragon