-1

有没有办法测试任意列表是否对称？

例如：

?- symmetric([a,b,b,a]).
true.

?- symmetric([a,b,c,a]).
false.

?- symmetric([a,a]).
true.

我的尝试是将第一个元素与最后一个元素进行比较，如果它们相等，则删除它们并继续处理列表的其余部分；否则失败。如果列表有 2 个元素并且它们相等，则成功。否则失败。

然而，使用这个谓词“找到”列表的结尾并不是真正的高效：

last(L,[L]).
last(L,[H|T]):-last(L,T).

有谁知道这样做的好方法？任何帮助将不胜感激！

顺便说一句：我不关心元素数量不均的列表。

4

2 回答 2

6

我找到了我的问题的答案。

对称列表是回文（有时您看不到只见树木不见森林）......这个简单的谓词测试：

is_palindrome(L) :- reverse(L,L).
于 2009-12-21T20:34:51.670 回答
2

但是您的算法仍然很有趣。有一个last/2内置的（至少在 SWI Prolog 中）不会受到递归方法的性能损失的影响。有了这个，这是一个实现您的想法的版本：

symmetric([]).
symmetric([L]).
symmetric([H|T]):-
    last(T,H),        % this forces the last element to equal the first
    append(T1,[H],T), % this deconstructs the rest list in one without the last elem.
    symmetric(T1).    % and recurses on that

有趣的是append/3谓词的使用，将初始剩余列表解构为没有最后一个元素的剩余列表。

编辑：我意识到即使没有 ，我也可以做到last/2，只需append/3. 所以这是改进的版本：

symmetric([]).
symmetric([L]).
symmetric([H|T]):-
    append(T1,[H],T), % deconstruct and assure symmetry
    symmetric(T1).    % and recurse

现在，这里append做了两个，解构得到 T1，以及确保列表的最后一个元素与第一个元素匹配:-)。

于 2009-12-22T13:03:48.080 回答