-1

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)

Sjoerd C. de Vries
  • 16,122
  • 3
  • 42
  • 94
Martynas
  • 43
  • 4

3 Answers3

6

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.}
Leonid Shifrin
  • 22,449
  • 4
  • 68
  • 100
  • Is there algorithm available online of this function? I need to make and application. – Martynas Jun 06 '11 at 14:44
  • @Martynas Unfortunately, I don't know what algorithm is used in `FindSequenceFunction`. Hopefully, more knowledgable people here will remark on that. – Leonid Shifrin Jun 06 '11 at 15:59
  • yeah, those are good, but there is fact, that I need to write my own application :) its the assignment ;] – Martynas Jun 06 '11 at 17:16
  • @Leonid Look what this guy is doing : http://www.rowan.edu/colleges/las/departments/math/facultystaff/nguyen/talks/Data%20Mining%20OEIS%20Math%20Dept%20Colloquium%20Feb%202011%20PDF.pdf – Dr. belisarius Jun 07 '11 at 03:23
  • @belisarius Thanks for the link, looks very interesting. I wonder to what extent this indeed can be automated. But in any case, Mathematica is definitely the right tool for the job. – Leonid Shifrin Jun 07 '11 at 12:43
4

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]

Plot of f

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.

Codie CodeMonkey
  • 7,669
  • 2
  • 29
  • 45
  • 1
    +1. It probably doesn't matter too much in your example, but it was pointed out to me [here](http://stackoverflow.com/questions/5610265/how-to-plot-a-gene-graph-for-a-dna-sequence-say-atgccgctgcgc/5644442#5644442) by Mark McClure that since version 6 you can use `Point@Transpose[{a, b}]` (rather than `Point /@ Transpose[{a, b}]`), and this syntax is much more efficient. You may already be aware of this. (I wasn't, until Mark pointed it out) – 681234 Jun 07 '11 at 11:56
4

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]

Sjoerd C. de Vries
  • 16,122
  • 3
  • 42
  • 94