Python 中的算术序列切片

Question

我正在尝试编写一个函数，它接受一个整数列表并在其中找到所有算术序列。

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

此列表中有五个算术序列：(0, 2), (2,4), (4, 6), (4,7), (5,7) - 这些是序列的第一个和最后一个元素的索引。一个序列是由元素之间的差异推导出来的。

正如您从上面的示例中看到的那样 - 序列必须长于 2 个元素（否则它会在每两个元素之间找到一个序列）。

我需要编写的函数必须 return 它在列表中找到的序列数 - 在这种情况下它应该 return 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 因为级数不能重叠。

两者都是 return 正确的输出，后者的效率要高得多：

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

Python 中的算术序列切片

Arithmetic Sequences Slices in Python

python

list

sequences