想象一下，有两组大小相同的数字。
是否有可能以及如何创建 一个函数 或算法来精确地将输入项映射到输出项的子例程？喜欢：
Input = 1, 2, 3, 4 Output = 2, 3, 4, 5
该函数将是：
f(x): return x + 1
通过“功能”，我的意思是比[1]稍微复杂一些：
f(x): if x == 1: return 2 if x == 2: return 3 if x == 3: return 4 if x == 4: return 5
这对于创建特殊的哈希函数或函数逼近很有用。
更新：
我试图问的是找出是否有一种方法可以 压缩 上面[1]中的琐碎映射示例。
找到输出某些字符串（序列，函数等）的最短程序等效于找到其Kolmogorov复杂度，这是无法确定的。
如果“不可能”不是令人满意的答案，则必须限制问题。在所有适当限制的情况下（多项式，有理函数，线性递归），只要您了解自己在做什么，就可以轻松找到最佳算法。例子：
多项式-Lagrange插值
有理函数-Pade逼近
布尔公式- 卡诺地图
近似解- 回归，线性案例：线性回归
数据的一般包装- 数据压缩 ; 有些技术（例如游程长度编码）是无损的，有些则不是。
对于多项式序列，通常有助于考虑序列b n = a n + 1 -a n；这将二次关系减少为线性关系，将线性关系减少为恒定序列等。但是没有灵丹妙药。您可以使用遗传算法，随机猜测，检查许多内置序列及其组成等，来构建一些启发式方法（例如Mathematica具有FindSequenceFunction-检查该页面以了解其复杂程度）。无论如何，由于Kolmogorov复杂性的不确定性，从理论上讲，任何这样的程序都离完美无穷。在实践中，您可能会得到满意的结果，但这需要很多人年。
另请参阅另一个SO问题。您还可以在应用程序中实现对OEIS的一些包装。
领域：
通常，可以做到的限制在
复杂性理论-描述可以“快速”解决的问题，例如找到图形中的最短路径，解决不了的问题，例如玩检查器的广义版本（它们是EXPTIME完整的）。
信息论-描述随机变量携带多少“信息”。例如，掷硬币。通常，要对结果进行编码需要1位，对n个结果进行编码需要n位（使用0-1长序列）。现在假设您有一个偏向硬币，它给尾巴提供90％的时间。然后，可能找到描述n个结果的另一种方法，该方法平均给出的序列要短得多。最佳编码所需的每个折腾的位数（在这种情况下小于1！）称为熵；该文章中的图显示了携带的信息量（1 / 2-1 / 2为1位，偏置硬币为1位，如果硬币始终位于同一侧则为0位）。
算法信息论-试图将复杂性理论和信息论结合起来。柯尔莫哥洛夫的复杂性就在这里。如果字符串具有很大的Kolmogorov复杂度，则可以考虑它为“随机”字符串：aaaaaaaaaaaaaa不是随机字符串，f8a34olx可能是随机字符串。因此，随机字符串是不可压缩的（Volchan的“什么是随机序列”是非常易读的介绍）。Chaitin的算法信息论该书可供下载。Quote：“ […]我们构建了一个仅包含整数，加法，乘法和乘幂运算的方程，其性质是，如果改变一个参数并询问解数是有限还是无限，则该问题的答案是与公平投掷硬币的独立结果没有区别。” （换句话说，没有算法可以猜测概率> 1/2的结果）。但是，我还没有读过那本书，所以无法评分。
与信息理论密切相关的是编码理论，它描述了纠错码。结果示例：可以将4位编码为7位，从而可以检测和纠正任何单个错误，或者检测两个错误（Hamming（7,4））。
“积极”方面是：
Lagrange插值和Pade逼近的符号算法是计算机代数/符号计算的一部分 ; Gerhard von zur Gathen的“现代计算机代数”是一个很好的参考。
数据压缩-在这里您最好向其他人寻求参考：）
