通过查找模式从序列生成下一个元素的算法 [英] An algorithm to generate the next element from a sequence, by finding a pattern

问题描述

我想知道是否可以列出一个数字列表，例如.

I was wondering if it is possible to take a list of numbers eg.

lst = [1, 1, 2, 3, 5, 8, 13, 21, 34]

并创建一种算法来弄清楚模式是什么:F(n) = F(n-1) + F(n-2)，然后继续并添加下一个数字:

And create an algorithm to figure out what the pattern is: the F(n) = F(n-1) + F(n-2) one and then keep going and add the next number:

lst.append(x) # x being the next number which is 55

可能是一种可以应用于任何数字列表的算法

Possibly an algorithm that could be applied to any list of numbers

推荐答案

简短的答案是:您要的是不可能的.

The short answer is: what you are asking for is impossible.

您正在寻找的是一种通常与曲线拟合有关的算法.对于此特定问题，一种可能的方法是 Lagrange多项式.

What you are looking for is an algorithm that relates to curve fitting in general. For this particular problem, one possible approach is Lagrange Polynomials.

但是请注意，通常来说，您想要的东西可能没有真正的解决方案.例如，考虑简单的序列:2, 4, 6, 8, 10, 12, 14.接下来的几个数字是什么?

But note that, in general, what you want may have no real solution. For example, consider the simple sequence: 2, 4, 6, 8, 10, 12, 14. What will the next few numbers be ?

您可能会说答案是16, 18, 20，依此类推，因为您使用等式f(n) = 2*n，其中n是术语的位置(从1开始).

You may say that the answer is 16, 18, 20 and so on, since you use the equation f(n) = 2*n where n is the location of the term (starting from 1).

请注意，方程式是无限的:

f(n) = [(n-1)*(n-2)*(n-3)*(n-4)*(n-5)*(n-6)*(n-7) * g(n)] + 2*n

第二项为n = 1..7生成正确的值，而第一项仅为n的那些值生成0.因此，您可以为第一项中的最后一个g(n)乘数选择任何函数(具有有限范围)，并从n=8开始获取所需的任何值.

The second term yields the right values for n = 1..7 while the first term yields a 0 for only those values of n. So you can choose any function (with finite range) for the last g(n) multiplier in the first term and get whatever values you want from n=8 onwards.

例如，使用g(n) = 20*n，

f(n) = (n-1)*(n-2)*(n-3)*(n-4)*(n-5)*(n-6)*(n-7) * 20 * n + 2*n

将产生一个列表:2, 4, 6, 8, 10, 12, 14, 806416

因此，您指出该问题无法解决.

Hence the problem as you state it is unsolvable.

但是，如果表征算法的形式(或表征要使用的函数族来解决问题)，则可以获得最适合数字的函数.例如，您可以说f(n)是阶数1(线性方程式)的多项式，这将减少可能性的数量并为您提供f(n) = 2 * n.其中一些方法传统上用于机器学习，尤其是线性回归和逻辑回归.

However, if you characterize the form of your algorithm (or characterize the function families that you wish to use, to solve the problem), you can get functions that optimally fit the numbers. For example, you could say that f(n) is a polynomial of order 1 (linear equation), which would reduce the number of possibilities and give you f(n) = 2 * n. Some of those approaches are used traditionally in Machine Learning, especially Linear and Logistic regression.

这篇关于通过查找模式从序列生成下一个元素的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！