检测和分解算术或几何序列的算法

Question

如果一个序列是纯算术序列（1,3,5,7,9...）或纯几何序列（3,9,27,81...），则很容易检测到。 “混合”算术/几何序列怎么样？

例如2 3 5 6 7 9 10 14
它包含 3 个算术序列 (3 6 9)、(3 5 7 9) 和 (2 6 10 14)。

例如2 3 4 8 9 16 27 32 81
它包含 2 个几何序列 (2 4 8 16 32) 和 (3 9 27 81)。

例如2 3 4 5 8 9 16 32
它包含 1 个几何数列 (2 4 8 16 32) 和 2 个算术数列 (2 3 4 5) (3 5 7 9)。

（假设序列应包含 2 个以上元素）

是否有任何算法可以检测（分析）上述混合序列并将其分解？即检测并列出其中的所有序列？ （假设原始序列包含 <= 20 integers)

谢谢。

注册
林志峰

Answer 1

由于原始序列具有

N<=20

，因此更容易对其进行暴力破解。您可以为此使用一个简单的算法：

l, n = your_input_list, number_of_elements
arithmetic_seq, geometric_seq = [], []
for i in [1, n]:
    for j in [i+1, n]:
        arithmetic, geometric = [l[i], l[j]], [l[i], l[j]]
        d = l[j] - l[i]
        r = l[j] / l[i]
        while (arithmetic[-1] + d) in l:
            arithmetic.append(arithmetic[-1] + d)
        while (geometric[-1] * r) in l:
            geometric.append(geometric[-1] * r)
        if arithmetic.length > 2:
            arithmetic_seq.append(arithmetic)
        if geometric.length > 2:
            geometric_seq.append(geometric)

肯定有一些极端情况需要您解决（留给读者作为练习），但这种方法应该适合您。

O(N^3)

顺序应该适用于小序列。对于较大的序列，您可以通过从右到左遍历序列来查看记忆，但这超出了本答案的范围。