Проблемы
(loop for number1 in sublist
for number2 in listB
when (= number1 number2)
do (setq candidate_sublist sublist)
finally (return candidate_list))
Как только в вашем списке совпадут два числа, вы заменяете candidate_sublist, даже если оно хуже, чем предыдущая привязка.Предположим, что candidate_sublist равно (0 2 3), что соответствует списку ввода (вы не можете быть более похожим, чем этот).Затем вы перебираете следующего кандидата (0 9 9).С вашим кодом, начиная с (= 0 0), вы меняете candidate_sublist.Вы действительно должны проверить все значения в обоих списках, которые сравниваются, прежде чем принимать решение.
Функция расстояния
Вы пытаетесь определить функцию сравнения среди списков: список лучше больше, чем другое, если больше похоже на данный список.Это можно реализовать, полагаясь на функцию расстояния.Следующий достаточно хорош:
(defun distance (a b)
(count nil (mapcar #'= a b)))
Или с циклом:
(defun distance (a b)
(loop
for aa in a
for bb in b
count (/= aa bb)))
Таким образом, чем больше различие между двумя списками, тем больше расстояние.
Частичные заказы
Это сравнение, однако, определяет частичный порядок, потому что вы можете легко иметь два списка, которые одинаково близки к входу.Например, приведен следующий список:
(0 1 2)
Оба (1 1 2) и (0 1 1) имеют одинаковое количество совпадающих значений.
Вы не можете просто вернуть одно best ответ, иначе вы выберете один из них на основе произвольного критерия (например, подробности реализации, такие как порядок обхода ваших списков).Что я хотел бы сделать, так это вычислить все списки, которые находятся на равном расстоянии от списка ввода.
(defun closest-lists (list candidates)
(loop
for candidate in candidates
for distance = (distance list candidate)
for better = T then (< distance min-distance)
for min-distance = (if better distance min-distance)
for best-matches = (cond
(better (list candidate))
((= distance min-distance) (cons candidate best-matches))
(t best-matches))
finally (return (values best-matches min-distance))))
Обобщение
Как сказано в комментариях @ Gwang-Jin Kim, closest-listsФункция может даже использоваться с другими функциями расстояния, если мы добавим ее в качестве параметра.Следуя соглашению о присвоении имен из sort, мы могли бы определить аргумент predicate, чтобы указать функцию сравнения, и аргумент key, чтобы указать, как получить сравниваемые значения (счет).Тогда наша функция на самом деле больше не связана со списками и может быть переименована, чтобы быть более общей:
(defun filter-by-score (candidates predicate &key (key #'identity))
"Keep elements from CANDIDATES having the same best rank according to PREDICATE.
PREDICATE should return non-NIL if its first argument precedes its
second one. Elements are compared according the value returned by
applying KEY. The KEY function is guaranteed to be applied once only
for each element in CANDIDATES."
(loop
for candidate in candidates
for score = (funcall key candidate)
for better = T then (funcall predicate score best-score)
for best-score = (if better score best-score)
for best-items = (cond
(better (list candidate))
((funcall predicate best-score score) best-items)
(t (cons candidate best-items)))
finally (return (values best-items best-score))))
Тогда наша предыдущая функция может быть выражена как:
(filter-by-score candidates #'< :key (lambda (u) (distance list u)))
Номы также можем сделать:
CL-USER> (filter-by-score '("a" "ab" "cd" "ed" "fe" "aaa" "bbb" "nnn")
#'> :key #'length)
("nnn" "bbb" "aaa")
3
Или даже:
CL-USER> (import 'alexandria:curry)
CL-USER> (ql:quickload :levenshtein)
CL-USER> (filter-by-score '("boat" "baobab" "brain" "biscuit")
#'<
:key (curry #'levenshtein:distance "ball"))
("brain" "boat")
3