algorithm - 为给定的输入和输出创建函数

Question

想象一下，有两组相同大小的数字。

是否有可能以及如何创建一个函数、算法或子程序，将输入项精确映射到输出项？喜欢:

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] 中那个简单的映射示例。

Answer 1

找到输出某些字符串(序列，函数等)的最短程序等效于找到其Kolmogorov complexity，这是不确定的。

如果“不可能”不是一个令人满意的答案，你必须限制你的问题。在所有适当限制的情况下(多项式、有理函数、线性递归)，只要您了解自己在做什么，就可以轻松找到最佳算法。例子:

多项式-Lagrange interpolation

有理函数 - Pade approximation

bool 公式 - Karnaugh map

近似解 - regression ，线性情况:linear regression

数据的一般打包 - data compression ;有些技术，如游程编码，是无损的，有些则不是。

在多项式序列的情况下，考虑序列bn=an+1-an通常会有所帮助；这将二次关系简化为线性关系，将线性关系简化为常数序列等。但没有 Elixir 。您可能会使用遗传算法，随机猜测，检查许多内置序列及其组成等来构建一些启发式方法(例如Mathematica的 FindSequenceFunction-检查该页面以了解其复杂程度)。无论如何，由于 Kolmogorov 复杂性的不可判定性，任何这样的程序——理论上——都离完美很远。在实践中，您可能会得到令人满意的结果，但这需要很多人年。

另见 another SO question 。您还可以在应用程序中为 OEIS 实现一些包装器。

领域:

大多数情况下，可以做的事情的限制在

复杂性理论 - 描述什么问题可以“快速”解决，比如在图中找到最短路径，什么不能，比如玩跳棋的通用版本(它们是 EXPTIME 完整的)。

信息论-描述随机变量携带多少“信息”。以抛硬币为例。通常，对结果进行编码需要 1 位，对 n 个结果进行编码需要 n 位(使用长 0-1 序列)。假设现在你有一个有偏见的硬币，它在 90% 的时间内给出了反面。然后，有可能找到另一种描述 n 个结果的方法，平均而言，它会给出更短的序列。最佳编码所需的每次抛掷位数(在这种情况下小于 1!)称为 entropy ； plot in that article 显示携带了多少信息(1/2-1/2 为 1 位，偏向硬币小于 1，如果硬币总是落在同一侧则为 0 位)。

算法信息理论 - 试图将复杂性理论和信息理论结合起来。柯尔莫哥洛夫的复杂性就在这里。如果字符串具有较大的 Kolmogorov 复杂度，您可以考虑“随机”字符串:aaaaaaaaaaaa 不是随机字符串，f8a34olx 可能是。因此，随机字符串是不可压缩的(Volchan's What is a random sequence 是一个非常易读的介绍。)。 Chaitin 的 algorithmic information theory 书可供下载。引用:“[...] 我们构造了一个仅涉及整数和加法、乘法和求幂的方程，其性质是如果改变一个参数并询问解的数量是有限的还是无限的，这个问题的答案是与独立抛硬币的结果没有区别。” (换句话说，没有算法可以猜测概率> 1/2的结果)。不过我没看过那本书，所以无法评价。

与信息论密切相关的是编码理论，它描述了纠错码。示例结果:可以将 4 位编码为 7 位，以便可以检测和纠正任何单个错误，或检测两个错误 ( Hamming(7,4) )。

“积极”的一面是:

用于拉格朗日插值和帕德逼近的

符号算法是 computer algebra/symbolic computation 的一部分； von zur Gathen、Gerhard 《现代计算机代数》是很好的引用。

数据压缩 - 在这里你最好向其他人寻求引用:)