algorithm - 查找数组之间双射的算法

Question

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

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

Answer 1

I don't think this problem has a general solution. You may try FindSequenceFunction, but it will not always find the solution. For the case at hand, you'd need a bit longer lists:

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

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

but

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

Out[251]= 2^n

You can also play with FindFit, if you have some guesses about the bijection:

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

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

Answer 2

Since you tag Mathematica, I'll use Mathematica functions as a reference.

If you are interested in an arbitrary fit of your data with a smooth function, you can use Interpolation. E.g.

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]

Interpolation uses piecewise polynomials. You can do the same in your favorite programming language if you happen know or are willing to learn a bit about numerical methods, especially B-Splines.

If instead you know something about your data, e.g. that it is of the form c d^x, then you can do a minimization to find the unknowns (c and d in this case). If your data is in fact generated from the form c d^x, then the fit will be fairly, otherwise it's the error is minimized in the least-squares sense. So for your data:

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

reports:

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

Indicating that your function is 2^x, just as you knew all along.

Answer 3

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

给出相同结果的其他可能函数是（可能还有无数其他函数）：(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 中使用以大写字母开头的变量，以免与保留字发生冲突]