Frage

Gibt es eine Möglichkeit zu testen, ob eine beliebige Liste symmetrisch ist?

Zum Beispiel:

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

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

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

Meine attemp war das erste Element das letzte Element zu vergleichen und, wenn sie gleich sind, sie zu entfernen und mit dem Rest der Liste gehen; sonst fehlschlagen. Erfolg haben, wenn die Liste 2 Elemente hat, und sie sind gleich. Andernfalls scheitern.

Allerdings „zu finden“, um das Ende der Liste dieses Prädikat verwendet, ist nicht wirklich performant:

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

Kennt jemand eine gute Möglichkeit, dies zu tun? Jede Hilfe wäre wirklich dankbar!

Btw:. Ich interessiere mich nicht für Listen mit einer ungeraden Anzahl von Elementen

War es hilfreich?

Lösung

fand ich die Antwort auf meine Frage.

Eine symmetrische Liste ist ein Palindrom (Manchmal sieht man nicht den Wald vor lauter Bäumen nicht sehen) ... Und diese einfache Prädikat Tests für das:

is_palindrome(L) :- reverse(L,L).

Andere Tipps

Aber Ihr Algorithmus war interessant dennoch. Es gibt einen last/2 eingebaut (zumindest in SWI Prolog), die nicht von der Leistungseinbuße des rekursiven Ansatz leidet. Damit ist hier eine Version, die Geräte Ihre Idee:

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

Interessant ist die Verwendung des append/3 Prädikats, die anfängliche Ruhe Liste in die Ruheliste ohne das letzte Element dekonstruieren.

EDIT: Ich erkannte ich ohne last/2 selbst tun kann, nur mit append/3. Also hier ist die verbesserte Version:

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

Nun, hier append beide nicht, die Dekonstruktion T1 zu erhalten, sowie zu gewährleisten, dass das letzte Element der Liste entspricht der erste: -).

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top