Я пытаюсь написать функцию в Scheme, которая принимает две строки в качестве входных данных и возвращает список всех оптимальных пар строк. Для этого я знаю, что мне нужно использовать следующие функции, которыеЯ уже написала, Уже написанные функции, очевидно, нужно будет использовать в качестве вспомогательных функций для функции, которую я пытаюсь написать.

1. оценка символов

Эта функция принимает две строки и оценивает каждый символ в соответствии с критериями оценки и накапливает результат. Если два символа равны, получается оценка 2, если два символа не равны, получается оценка -1, и, наконец, если один символ является подчеркиванием, а другой - что-то еще, оценка -2 получается.

Вот пример ввода / вывода:

> (score-chars "x" "x")
2

> (score-chars "x" "y")
-1

> (score-chars "x" "_")
-2

> (score-chars "Cheese" "Computer")
-3  

2. пары переменная строка

Эта функция принимает два символа (скажем, a и b) и список пар строк в качестве входных данных и возвращает модифицированный список пар строк: для каждой пары строк в списке.

Вот пример ввода / вывода:

> (change-string-pairs "a" "b" '(("one" "two")("three" "four")("five" "six")))
(("aone" "btwo") ("athree" "bfour") ("afive" "bsix"))

3. получить лучшие пары

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

Вот пример ввода / вывода:

> (get-best-pairs score-chars '(("cheese" "cake")("door" "wall")("bunny" "roof")("mouse" "house")("photo" "video")))
(("mouse" "house"))

Имея все эти функции, описанные выше, которые я уже написал, функция, которую я пытаюсь написать с использованием этих функций, будет иметь следующее:

Ввод, вывод:

> (get-all-best-pairs "many" "penny")
(("man_y" "penny") 
 ("ma_ny" "penny") 
 ("m_any" "penny") 
 ("_many" "penny")) 

Было бы здорово, если бы я мог получить общее представление о том, как это можно сделать. Кроме того, в моих функциях, которые я написал выше, я использовал некоторые встроенные функции Scheme, такие как map, filter, append и apply.

Мне также известно, что алгоритм крайне неэффективен и имеет экспоненциальную сложность. Это не беспокоит меня в это время.

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