Пролог: проверить, является ли произвольный список симметричным - PullRequest
Новая
       27

Пролог: проверить, является ли произвольный список симметричным

0 голосов
/ 21 декабря 2009

Есть ли способ проверить, является ли произвольный список симметричным?

Например: 

?- 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).

Кто-нибудь знает хороший способ сделать это? Любая помощь будет принята с благодарностью!

Кстати: мне плевать на списки с неравным количеством элементов.

Ответы [ 2 ]

6 голосов
/ 21 декабря 2009

Я нашел ответ на свой вопрос.

Симметричный список - это палиндром (иногда вы не видите лес за деревьями) ... И этот простой предикатный тест для этого: 

is_palindrome(L) :- reverse(L,L).
2 голосов
/ 22 декабря 2009

Но ваш алгоритм все же был интересен. Существует встроенный 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, а также обеспечивает соответствие последнего элемента списка первому: -).

...