给定一组数字，找到其中最长算术进度的长度。

Question

我的做法如下：
1. 我正在创建一个存储所有数字对之间差异和计数的字典
2. 键包含差值，值是一个列表。列表的第一个索引是差值出现的次数，后续索引表示遵循等差数列的数字

我已经编写了以下代码。

d = {}
for i in range(len(A)-1):
    for j in range(i+1, len(A)):
        if A[i]-A[j] in d.keys():
            d[A[i]-A[j]][0] += 1
            d[A[i]-A[j]].append(A[j])
        else:
            d[A[i]-A[j]] = [2, A[i], A[j]]
# Get the key,value pair having the max value
k,v  = max(d.items(), key=lambda k: k[1])
print(v[0])

例如，如果输入为[20,1,15,3,10,5,8]，则输出为4。

但是，我的代码在以下输入[83,20,17,43,52,78,68,45]中失败了。 期望的结果是2，但我得到了3。当我打印我的字典内容时，我发现在字典中有像下面这样的条目：

-25: [3, 20, 45, 68], -26: [3, 17, 43, 78], -35: [3, 17, 52, 78]

我不理解为什么它们存在，因为在-25的情况下，68和45的差不是25，而且我在将值添加到字典之前就进行了检查。 请问有人能指出我的代码中的错误吗？

我的完整输出如下：

{63: [2, 83, 20], 66: [2, 83, 17], 40: [2, 83, 43], 31: [2, 83, 52], 5: [2, 83, 78], 15: [2, 83, 68], 38: [2, 83, 45], 3: [2, 20, 17], -23: [2, 20, 43], -32: [2, 20, 52], -58: [2, 20, 78], -48: [2, 20, 68], -25: [3, 20, 45, 68], -26: [3, 17, 43, 78], -35: [3, 17, 52, 78], -61: [2, 17, 78], -51: [2, 17, 68], -28: [2, 17, 45], -9: [2, 43, 52], -2: [2, 43, 45], -16: [2, 52, 68], 7: [2, 52, 45], 10: [2, 78, 68], 33: [2, 78, 45], 23: [2, 68, 45]}

- Jitesh Malipeddi

---

当i = 3时，你的A[i] = 43，而j的变化范围为4到7。因此，在j = 6时，A[j]变为68，然后差值为-25。问题在于你的算法不关心差异来自哪里。它可能在列表中的任意两个数字之间，这不是等差数列。 - Salil

Answer 1

我认为您所使用的算法不能解决您想要解决的问题。主要问题在于扩展算术序列的标准没有考虑到序列本身。例如，请考虑：

A = [10, 20, 50, 60]

有两个序列属于差异-10，因此dict实际上不是一个好的数据结构来基于你打算的算法。

---

编辑

您可以通过多种方式解决问题。一种非常直接但不太高效的方法如下：

• 对所有元素进行排序（这不是必需的，但它使其他操作更加高效）
• 从考虑所有元素开始
• 确定所有元素是否实际上是等差数列
  • 仅计算相邻元素之间的差异
  • 如果它们都具有相同的值，则为等差数列
• 如果它们是等差数列，则完成了，如果不是，则迭代地删除元素并重复上述操作，直到找到等差数列。

在代码中，它看起来像：

import itertools


def is_arithmetic_progression(items):
    diffs = [x - y for x, y in zip(items[1:], items[:-1])]
    return diffs[1:] == diffs[:-1]


def skip_items(items, indexes):
    return [item for i, item in enumerate(items) if i not in indexes]


def lap_combs(items, sorting=True):
    if sorting:
        items = sorted(items)
    for i in range(len(items)):
        for indexes in itertools.combinations(range(len(items)), i):
            new_items = skip_items(items, indexes)
            if is_arithmetic_progression(new_items, False):
                return new_items


items = [83, 20, 17, 43, 52, 78, 68, 45]
longest_ap = lap_combs(items)
print(longest_ap)
# [78, 83]

items = [83, 20, 17, 43, 52, 78, 68, 45, 70]
longest_ap = lap_combs(items)
print(longest_ap)
# [20, 45, 70]

---

编辑2:

请注意，通过分析排序项目之间的差异，可能可以进一步优化：

• 计算任意两个项目之间的所有差异
• 对于给定的差异，计算有多少元素在项目中
• 跟踪找到的给定项目和元素的最大元素数
• 如果对于给定的差异，项目不能包含更多数字，则跳过它
• 如果元素的数量超过项目数量的一半，则停止

在代码中，看起来像这样：

def seed_diff_len_to_seq(seed, diff, length):
    return [seed + diff * k for k in range(length)]


def lap_diffs(items):
    half_len_items = len(items) // 2
    span = max(items) - min(items)
    seed = 0
    max_seq_len = 0
    diff = None
    set_items = set(items)
    for item_i, item_j in itertools.combinations(sorted(items), 2):
        diff_ji = item_j - item_i
        if diff_ji == 0:
            seq_len = sum(1 for item in items if item == item_i)
        elif abs(diff_ji * max_seq_len) > span:
            continue
        else:
            seq_len = 2
            while item_i + diff_ji * seq_len in set_items:
                seq_len += 1
        if seq_len > max_seq_len:
            max_seq_len = seq_len
            seed = item_i
            diff = diff_ji
            if seq_len > half_len_items:
                break
    return seed_diff_len_to_seq(seed, diff, max_seq_len)

---

对此进行基准测试（包括使用@VPfB的解决方案作为lap_maxprogr()和@rusu_ro1的解决方案作为lap_dict()，而lap_combs()至少比它们慢一个数量级，并且不包含在图表中）表明，lap_diffs()是最快的（一旦输入项的数量超过大约十几个）：

完整分析在这里。

请注意，lap_diffs()与lap_maxprogr()使用基本相同的方法，只是有更多的优化。

- norok2

---

@JiteshMalipeddi 请查看 EDIT 2，其中包括基准测试。 - norok2

Answer 2

请注意：

1. 您的列表中有43个元素，68-43 = 25
2. 存在多个具有相同差异的LPA

存在两个错误：

1. 您检查了差异是否存在于d.keys()中，但没有检查数字是否在LPA中。例如：当数字为43、68时，差异为25，但当前列表为[2、20、45]。在这种情况下，存在多个具有相同差异25的LAP。
2. 您插入了A[j]，但没有插入A[i]，因此只插入了68，而不是43。

- hunzter

Answer 3

你必须意识到数字之间的差异不足以作为关键字，例如8-3=5，同时5-0=5。

你可以尝试：

def length_longest_AP(A):
    d = {}
    A.sort()
    for index_i, i in enumerate(A[:-1]):
        for index, j in enumerate(A[index_i + 1 :]):
            dif = j - i
            key = f'{i}_{index_i}_{dif}'

            if key in d:
                continue


            d[key] = [i, j]
            possible_next = j + dif
            try:
                current_index = index_i + 1 + index
                possible_next_one_index = current_index + A[current_index + 1:].index(possible_next)

                # avoiding repetitions 
                if current_index == possible_next_one_index:
                    possible_next_one_index = current_index + 1

            except ValueError:
                continue

            while True:
                d[key].append(possible_next)
                possible_next += dif
                try:
                    current_index = possible_next_one_index
                    possible_next_one_index = current_index + A[current_index + 1:].index(possible_next)

                    # avoiding repetitions 
                    if current_index == possible_next_one_index:
                        possible_next_one_index = current_index + 1

                except ValueError:
                    break


    return len(max(d.values(), key=len))

print(length_longest_AP([20,1,15,3,10,5,8]))
print(length_longest_AP([1,1,1,1,1,1,1,1,1,1]))
print(length_longest_AP([83,20,17,43,52,78,68,45]))

输出：

4
10
2

- kederrac

Answer 4

另一种方法。将每对作为一个进展的开端，并尝试扩展该进展。

重要优化：如果一个进展包含至少总项目数量的一半，则它必须是可能的最长进展。

import itertools

def maxprogr(items):
    # 2 or more numbers required to find any progression
    # if there are multiple maximums, the first one is returned 
    half = len(items) / 2
    pmax = (None, None, 0)
    for start, stop in itertools.combinations(sorted(items), 2):
        diff = stop - start
        if diff == 0:
            plen = sum(1 for x in items if x == start) 
        else:        
            plen = 2 
            while start + diff*plen in items:
                plen += 1
        if plen > pmax[2]:
            pmax = (start, diff, plen)
        if plen > half:
            break
    return pmax

# and some tests:
def print_maxprogr(items):
    print("MAX: start={0[0]}, diff=+{0[1]}, len={0[2]}".format(maxprogr(items)))

test1 = [20,1,15,3,10,5,8]
print_maxprogr(test1)
test2 = [83, 20, 17, 43, 52, 78, 68, 45, 70] 
print_maxprogr(test2)
test3 = [83, 20, 17, 43, 52, 78, 68, 45]
print_maxprogr(test3)
test4 = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
print_maxprogr(test4)

测试输出：

MAX: 开始=5，差值=+5，长度=4
MAX: 开始=20，差值=+25，长度=3
MAX: 开始=17，差值=+3，长度=2
MAX: 开始=1，差值=+0，长度=10

（代码在发布后1小时内更新以修复小错误）

- VPfB