-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 に答える