查找数组之间双射的算法

Question

我有两个数组，例如 A={1, 2, 3} 和 B={2, 4, 8} （数组项计数和数量可能会有所不同）。如何找到数组之间的双射。

在这种情况下，它将是 f:A->B; f(x)=2^(x)

Answer 1

我认为这个问题没有通用的解决方案。您可以尝试 FindSequenceFunction，但它并不总能找到解决方案。对于当前的情况，您需要更长的列表：

In[250]:= FindSequenceFunction[Transpose[{{1, 2, 3}, {2, 4, 8}}], n]

Out[250]= FindSequenceFunction[{{1, 2}, {2, 4}, {3, 8}}, n]

但是

In[251]:= FindSequenceFunction[Transpose[{{1, 2, 3, 4}, {2, 4, 8, 16}}], n]

Out[251]= 2^n

如果您对双射有一些猜测，您也可以使用 FindFit：

In[252]:= FindFit[Transpose[{{1, 2, 3}, {2, 4, 8}}], p*q^x, {p, q}, x]

Out[252]= {p -> 1., q -> 2.}

Answer 2

正如其他人所说，这个问题的定义不明确。

给出相同结果的其他可能的函数有（可能还有无数其他函数）： (8 x)/3 - x^2 + x^3/3, x + (37 x^2)/18 - (4 x^3) /3 + (5 x^4)/18 和 (259 x^3)/54 - (31 x^4)/9 + (35 x^5)/54。

我发现这些解决方案使用：

n = 5; (* try various other values *)
A = {1, 2, 3} ; B = {2, 4, 8}
eqs = Table[
  Sum[a[i] x[[1]]^i, {i, n}] == x[[2]], {x, {A, B}\[Transpose]}]
sol = Solve[eqs, Table[a[i], {i, n}], Reals]
Sum[a[i] x^i, {i, n}] /. sol

有时并非所有 a[i] 都完全确定，您可能会想出自己的值。

[提示：在 Mathematica 中最好不要使用以大写字母开头的变量，以免与保留字发生冲突]

Answer 3

既然您标记了 Mathematica，我将使用 Mathematica 函数作为参考。

如果您对使用平滑函数任意拟合数据感兴趣，则可以使用插值。例如

a = {1, 2, 3}; b = {2, 4, 8};
f = Interpolation[Transpose[{a, b}]];

(* Graph the interpolation function *)
Show[Plot[f[x], {x, 1, 3}], Graphics[Point /@ Transpose[{a, b}]], 
   PlotRange -> {{0, 4}, {0, 9}}, Frame -> Automatic, Axes -> None]

插值使用分段多项式。如果您碰巧了解或愿意学习一些数值方法（尤其是 B 样条曲线），您可以使用您最喜欢的编程语言执行相同的操作。

相反，如果您对数据有所了解，例如数据的形式为 cd^x，那么您可以进行最小化来查找未知数（在本例中为 c 和 d）。如果您的数据实际上是从 cd^x 形式生成的，那么拟合将是公平的，否则误差在最小二乘意义上被最小化。因此，对于您的数据：

FindFit[Transpose[{a, b}], c d^x, {c, d}, {x}]

报告：

{c -> 1., d -> 2.}

表明您的函数是 2^x，正如您一直知道的那样。