Алгоритм нахождения биекции между массивами

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, если у вас есть некоторые предположения о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

Как уже отмечали другие, эта проблема плохо определена.

Другими возможными функциями, которые дают те же результаты, являются (среди, вероятно, бесконечные другие): (8 x) / 3 - x ^ 2 + x ^ 3/3, x + (37 x ^ 2) / 18 - (4 x ^ 3) / 3 + (5 х ^ 4) / 18 и (259 х ^ 3) / 54 - (31 х ^ 4) / 9 + (35 х ^ 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-Splines.

Если вместо этого вы что-то знаете о своих данных, например, что он имеет форму c d ^ x, тогда вы можете сделать минимизацию, чтобы найти неизвестные (в данном случае c и d). Если ваши данные на самом деле сгенерированы из формы c d ^ x, то подгонка будет справедливой, в противном случае ошибка минимизируется в смысле наименьших квадратов Итак, для ваших данных:

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

Отчеты:

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

Указывает, что ваша функция 2 ^ x, как вы и раньше знали.