Арифметические последовательности в Python

Question

Я пытаюсь написать функцию, которая берет список целых чисел и находит в ней все арифметические последовательности.

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

Есть пять арифметических последовательностей в этом списке: (0, 2), (2,4), (4, 6), (4,7), (5,7) - это индексы первого и последнего элемента последовательности. Последовательность определяется разницей между элементами.

Как видно из приведенного выше примера, последовательность должна быть длиннее 2 элементов (иначе она найдет последовательность между каждыми двумя элементами).

Функция, которую мне нужно писать должен возвращать число последовательностей он находит в списке - в этом случае он должен вернуть 5.

Я вроде застрял - попробовал несколько различных подходов, но с треском провалились , Самое последнее, что я сделал это:

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) 

я испортил что-то перебор X, в данный момент время, это бесконечный цикл.

Answer 1

Может быть, вы можете использовать логику, как это -

>>> 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)] 

Answer 2

грубой силы подход просто проверить каждый ломтик> Len 3, для каждого среза вам просто нужно вычесть первый и последний элемент, чтобы получить разница и посмотреть, если все a[i+1] - A[i] равны разнице:

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)) 

более эффективная версия:

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 - максимальное количество срезов, которое может быть сформировано для любой прогрессии длины> = 3, мы устанавливаем st = end, потому что никакие прогрессии не могут перекрываться.

Оба возвращают правильный вывод, последний раз значительно более эффективным:

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