algorithm - 配列間の全単射を見つけるアルゴリズム

Question

私は2つの配列、たとえば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

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であることを示します。

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では大文字で始まる変数を使用しない方がよい]