Turbo Prolog：通过向列表添加最少数量的字符来创建回文

Question

Turbo Prolog 上有一段代码可以从整个输入列表创建回文。

需要通过向列表中添加最少的字符来构建回文。

例如，我们输入一个列表 [1, 2, 3, 4, 3] ，在退出时而不是 [1, 2, 3, 4, 3, 4, 3, 2, 1] 应该计算出 [1 , 2, 3, 4, 3, 2, 1]（也就是说，程序应该将缺失的元素添加到回文中，而不是从整个输入的列表中构建它）

帮助

此代码从整个输入列表创建一个回文：

domains
  list = integer*
 
predicates
  readlist(list).
  extend_to_palindrome(list, list).
  reverse(list, list).
  append(list, list, list).
  suffix(list, list).
 
clauses
  readlist([Head|Tail]) :-
    readint(Head), !,
    readlist(Tail).
  readlist([]).
 
  reverse([], []).
  reverse([H|T], Reversed) :-
    reverse(T, ReversedTail),
    append(ReversedTail, [H], Reversed).
 
  append([], List, List).
  append([H|T], List2, [H|Result]) :-
    append(T, List2, Result).
 
  suffix(List, Suffix) :-
    append([], Suffix, List).
 
  extend_to_palindrome(List, Result) :-
    suffix(List, Suffix),
    reverse(Suffix, [_|TrimmedReversedSuffix]),
    append(List, TrimmedReversedSuffix, Result).
 
goal
  write("Enter elements: "), nl,
  readlist(List),
  extend_to_palindrome(List, Palindrome),
  write("Palindrome: "), write(Palindrome), nl.

Answer 1

reverse(Suffix, [_|TrimmedReversedSuffix])

- 在 SWI Prolog 中，

_

只能是单个事物；如果 Turbo Prolog 中的值相同，则不会修剪不同的数量，并且不会搜索更短或更长的答案。

extend_to_palindrome/2

不测试列表是否是回文，因此它无法检查其他可能的解决方案。

在这个示例代码中，我使用带有回溯的append/3从列表左侧搜索可变数量，反转它然后再次使用append，并使用reverse来测试结果是否是回文（反转它不会改变它）。

Ls = [1,2,3,4,3],

append(Left, _, Ls)            % take variable amount from left,

reverse(Left, Right),          % reverse it,
append(Ls, Right, Result),     % stick it to the right.

reverse(Result, Result)        % it must make a palindrome.

这将尝试附加 [], [1], [2,1], [3,2,1], [4,3,2,1], [3,4,3,2,1] 并挑选构成回文的那些，首先是最短的。