Ответ в теме: Самая длинная последовательность в Xs, которая состоит из Ys

      Комментарии к записи Ответ в теме: Самая длинная последовательность в Xs, которая состоит из Ys отключены
#2428

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

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

longest_subsequence(List, Part, Subsequence):-
  longest_subsequence_(List, Part, [], Subsequence).

Вспомогательная функция состоит из двух правил — первое пытается добавить к накапливающему параметру список Ys и найти полученный результат в списке Xs. Если это удается — выполняется рекурсивный вызов с увеличенным накапливающим параметром, иначе — управление передается второму правилу. Второе правило выполняется лишь один раз (т.к. не содержит рекурсивных вызовов) — если увеличить накапливающий параметр уже не удалось. В этом случае ясно, что содержание накапливающего параметра уже является результатом работы функции и его остается лишь вернуть:
longest_subsequence_(Xs, Ys, CurrentSubsequence, LongestSubsequence):-
  append(CurrentSubsequence, Ys, NextSubsequence),
  divide_list(Xs, [_LeftYs, NextSubsequence, _RightYs]), !,
  longest_subsequence_(Xs, Ys, NextSubsequence, LongestSubsequence).
longest_subsequence_(_Xs, _Ys, LongestSubsequence, LongestSubsequence).

Вложения: