Создать функцию для заданного ввода и вывода

Question

Представьте себе, есть два набора чисел одинакового размера.

Возможно ли и как создать функцию алгоритм или подпрограмму, которая точно отображает элементы ввода в элементы вывода? Как:

Input = 1, 2, 3, 4
Output = 2, 3, 4, 5

и функция будет:

f(x): return x + 1

И под «функцией» я подразумеваю нечто более сложное, чем [1]:

f(x):
    if x == 1: return 2
    if x == 2: return 3
    if x == 3: return 4
    if x == 4: return 5

Это было бы полезно для создания специальных хеш-функций или приближений функций.

---

Обновление:

Я пытаюсь спросить, есть ли способ сжать этот тривиальный пример отображения сверху [1].

Answer 1

Нахождение самой короткой программы, которая выводит некоторую строку (последовательность, функцию и т. Д.), Эквивалентно нахождению ее колмогоровской сложности , которая неразрешима.

Если «невозможно» не является удовлетворительным ответом, вы должны ограничить свою проблему. Во всех соответствующим образом ограниченных случаях (полиномы, рациональные функции, линейные повторения) найти оптимальный алгоритм будет легко, если вы понимаете, что делаете. Примеры:

• полином - интерполяция Лагранжа

• рациональная функция - аппроксимация Паде

• логическая формула - Карта Карно

• приблизительное решение - регрессия , линейный случай: линейная регрессия

• общая упаковка данных - сжатие данных ; некоторые методы, такие как кодирование по длине прогона, без потерь, а некоторые нет.

В случае полиномиальных последовательностей часто помогает рассмотреть последовательность b _n = a _{n + 1} -a _n ; это уменьшает квадратичное отношение к линейному, а линейное - к постоянной последовательности и т. д. Но серебряной пули нет. Вы можете построить некоторую эвристику (например, Mathematica имеет FindSequenceFunction - проверьте эту страницу, чтобы получить представление о том, насколько сложной это может быть), используя генетические алгоритмы, случайные догадки, проверяя множество встроенных последовательностей и их составов и т. Д. , Несмотря ни на что, любая такая программа - в теории - бесконечно далека от совершенства из-за неразрешимости колмогоровской сложности. На практике вы можете получить удовлетворительные результаты, но это требует много человеко-лет.

См. Также еще один вопрос SO . Вы также можете внедрить некоторую оболочку для OEIS в своем приложении.

Поля:

В основном, пределы того, что можно сделать, описаны в

• теория сложности - описание того, какие проблемы могут быть решены «быстро», например, поиск кратчайшего пути в графе, а что нет, например, воспроизведение обобщенных версий шашек (они завершены EXPTIME).

• теория информации - описание того, сколько «информации» переносится случайной величиной. Например, возьмите монетку. Обычно для кодирования результата требуется 1 бит, а для кодирования n результатов - n битов (используется длинная последовательность 0-1). Предположим теперь, что у вас есть предвзятая монета, которая дает хвосты 90% времени. Затем можно найти другой способ описания n результатов, который в среднем дает гораздо более короткую последовательность. Количество бит на бросок, необходимое для оптимального кодирования (в этом случае меньше 1!), Называется entropy ; график в этой статье показывает, сколько информации переносится (1 бит для 1 / 2-1 / 2, меньше 1 для смещенной монеты, 0 бит, если монета приземляется всегда на одной стороне).

• алгоритмическая теория информации - которая пытается объединить теорию сложности и теорию информации. Колмогоровская сложность относится сюда. Вы можете считать строку «случайной», если она имеет большую колмогоровскую сложность: aaaaaaaaaaaa не случайная строка, вероятно, f8a34olx. Таким образом, случайная строка несжимаема ( Что такое случайная последовательность Волчана - очень читаемое введение.). * * * * * * * * * * * * * * * книга алгоритмической теории информации . Цитата: «[...] мы строим уравнение, включающее только целые числа и сложение, умножение и возведение в степень со свойством, что если кто-то изменяет параметр и спрашивает, является ли число решений конечным или бесконечным, ответ на этот вопрос неотличим от результата независимых бросков честной монеты ". (другими словами, никакой алгоритм не может угадать этот результат с вероятностью> 1/2). Однако я не читал эту книгу, поэтому не могу оценить ее.

С теорией информации тесно связана теория кодирования, которая описывает коды, исправляющие ошибки. Пример результата: возможно закодировать от 4 до 7 битов, чтобы можно было обнаружить и исправить любую отдельную ошибку или обнаружить две ошибки ( Хэмминга (7,4) ).

«Положительной» стороной являются:

• символьные алгоритмы для интерполяции Лагранжа и аппроксимации Паде являются частью компьютерной алгебры / символьных вычислений ; von zur Gathen, Герхард "Современная компьютерная алгебра" - хороший справочник.

• сжатие данных - здесь вам лучше обратиться к кому-нибудь еще за ссылками:)

Answer 2

Хорошо, я не понимаю ваш вопрос, но я собираюсь дать ему шанс.

Если у вас есть только 2 набора чисел и вы хотите найти f, где y = f (x), то вы можете попробовать подбор кривой , чтобы получить приблизительную «карту».

В этом случае он линейный, поэтому подгонка кривой будет работать. Вы можете попробовать разные модели, чтобы увидеть, какая из них работает лучше всего, и выбрать на основе минимизации метрики ошибки.

Это то, что вы имели в виду?

Вот еще одна ссылка на подгонка кривой и изображение из этой статьи:

Answer 3

Мне кажется, что вы хотите хеш-таблицу . Они основаны на хеш-функциях, и есть известные хеш-функции, которые работают лучше, чем другие, в зависимости от ожидаемого ввода и желаемого вывода.

Если вам нужен алгоритмический способ сопоставления произвольного ввода с произвольным выводом, это неосуществимо в общем случае, поскольку полностью зависит от набора ввода и вывода.

Например, в имеющемся у вас тривиальном примере функция сразу очевидна, f(x): x+1. В других случаях может быть очень сложно или даже невозможно сгенерировать точную функцию, описывающую отображение, вам придется аппроксимировать или просто использовать карту напрямую.

Answer 4

Распознавание базовой карты по входным и выходным данным - это как раз то, чем занимаются нейронные сети! Вы неосознанно наткнулись на большое направление исследований в области компьютерных наук.

Answer 5

Делать это в общем случае произвольно сложно. Например, рассмотрим блочный шифр, используемый в режиме ECB: он отображает входное целое число в выходное целое число, но - из-за замысла - вывод любого общего отображения из конкретных примеров невозможен. Фактически, для хорошего шифра, даже с полным набором отображений между входными и выходными блоками, вы все равно не могли определить, как рассчитать это отображение на общих основаниях.

Очевидно, что шифр является крайним примером, но он служит для иллюстрации того, что не существует (известной) общей процедуры выполнения того, что вы просите.

Answer 6

В некоторых случаях (например, в вашем примере), линейная регрессия или аналогичные статистические модели могут найти связь между вашими входными и выходными наборами.