Algorithm to find bijection between arrays

I have two arrays, say A={1, 2, 3} and B={2, 4, 8}开发者_如何学编程 (array item count and numbers may vary). How do I find a bijection between the arrays.

In this case, it would be f:A->B; f(x)=2^(x)

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.}

As others have remarked, this problem is ill-defined.

Other possible functions that give the same results are (among probably infinite others): (8 x)/3 - x^2 + x^3/3, x + (37 x^2)/18 - (4 x^3)/3 + (5 x^4)/18, and (259 x^3)/54 - (31 x^4)/9 + (35 x^5)/54.

I found these solutions using:

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

Sometimes not all of the a[i]'s are fully determined and you may come up with values of your own.

[tip: better not use variables starting with a capital letter in Mathematica so as not to get into conflict with reserved words]

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.