CODEWITHSUNDEEP
pythonlistsequences
mr0
mr0

Reputation: 43

Arithmetic Sequences Slices in Python

I'm trying to write a function that takes a list of integers and finds all arithmetic sequences in it. 

A = [-1, 1, 3, 3, 3, 2, 1, 0]

There are five arithmetic sequences in this list: (0, 2), (2,4), (4, 6), (4,7), (5,7) - these are indexes of first and last element of a sequence. A sequence is derived by the difference between elements.

As you see from the example above - the sequence must be longer than 2 elements (otherwise it would find a sequence between every two elements).

The function that I need to write must return the number of sequences it finds on the list - in this case it should return 5.

I'm kind of stuck - tried a few different approaches but failed miserably. The most recent thing I've done is:

def solution(A):
slices = []
x = 0
listlen = len(A)
while x < listlen-1:
    print ("Current x:", x)
    difference = A[x+1] - A[x]
    #print ("1st diff: ", A[x+1], ",", A[x], " = ", difference)
    for y in range(x+1, len(A)-1):
        difference_2 = A[y+1] - A[y]
        #print ("Next Items: ", A[y+1], A[y])
        #print ("2nd diff: ", difference_2)
        if (difference == difference_2):
            #print ("I'm in a sequence, first element at index", x)
        else:
            #print ("I'm leaving a sequence, last element at index ", y)
            slice = str(x) + "," + str(y)
            slices.append(slice)
            x += 1
            #print ("Changing X to find new slice: x:", x)
            break
print (slices)

I messed something up with iterating X, at this point in time, it's an endless loop.

Upvotes: 1

Views: 2267

Answers (2)

Padraic Cunningham
Padraic Cunningham

Reputation: 180481

a brute force approach is to just check each slice > len 3, for each slice you just need to subtract the first and last element to get the difference and see if all a[i+1] - A[i] are equal to the difference:

def is_arith(x):
    return all(x[i + 1] - x[i] == x[1] - x[0]
                for i in range(len(x) - 1))

def arith_count(A):
    return sum(is_arith(A[i:j])for i in range(len(A))
               for j in range(i + 3,len(A)+1))

A more efficient version:

def arith_sli(A):
    n = len(A)
    st,tot = 0, 0
    while st < n - 2:
        end = st + 1
        dif = A[end] - A[st]
        while end < n - 1 and A[end + 1] - A[end] == dif:
            end += 1
        ln = end - st + 1
        if ln >= 3:
            tot += (ln - 2) * (ln - 1) // 2
        st = end
    return tot

tot += (ln - 2) * (ln - 1) // 2 is the max number of slices that can be formed for any length progression >= 3, we set st = end because no progressions can overlap.

Both return the correct output, the latter is just considerably more efficient:

In [23]: A = [-1, 1, 3, 3, 3, 2, 1, 0]
In [24]: arith_sli(A)
Out[24]: 5    
In [25]: arith_count(A)
Out[25]: 5     
In [26]: A = [-1, 1, 3, 3, 4, 2, 1, 0,1,2]
In [27]: arith_sli(A)
Out[27]: 3    
In [28]: arith_count(A)
Out[28]: 3

Upvotes: 1

Anand S Kumar
Anand S Kumar

Reputation: 90979

Maybe you can use a logic like this -

>>> A = [-1, 1, 3, 3, 3, 2, 1, 0]
>>> def indices(l):
...     res = []
...     for i in range(0,len(l)-2):
...             diff = l[i+1] - l[i]
...             for j in range(i+2,len(l)):
...                     if (l[j] - l[j-1]) == diff:
...                             res.append((i,j))
...                     else:
...                             break;
...     return res
...
>>> indices(A)
[(0, 2), (2, 4), (4, 6), (4, 7), (5, 7)]

Upvotes: 1

Related Questions