Eliminuj kolejne duplikaty elementów listy za pomocą prologu

Nov 27 2020

Pierwotnym problemem było wymyślenie sposobu na uzyskanie następujących rzeczy

remove([a,a,a,b,q,q,q,q,e,e,e]),X)
X = [a,b,q,e]

Odpowiedzi

1 rajashekar Nov 28 2020 at 05:20

Możemy rozwiązać ten problem, wykonując jedną iterację wzdłuż listy. W dowolnym miejscu na liście sprawdzamy aktualny element i następny element, jeśli są takie same, to ignorujemy bieżący element, w przeciwnym razie, jeśli są różne, bierzemy bieżący element.

rm_dup([], []).
rm_dup([X], [X]).
rm_dup([X1, X2 | Xs], [X1 | Ys]) :-
    dif(X1, X2), rm_dup([X2|Xs], Ys).
rm_dup([X, X | Xs], Ys) :-
    rm_dup([X | Xs], Ys).

Pierwsza i druga klauzula to klauzule podstawowe, w których nie ma zduplikowanych elementów. Trzecia i czwarta klauzula to reguły rekurencyjne.

W trzeciej klauzuli stwierdzamy, że jeśli lista wejściowa ma dwie wartości X1i X2i są one różne dif(X1, X2), to zachowaj bieżącą wartość.

W czwartej klauzuli, jeśli mamy te same kolejne wartości, to ignorujemy bieżącą wartość.

Trzecia i czwarta klauzula wykluczają się wzajemnie, dlatego aby predykat był deterministyczny, lepiej połączyć je w następujący sposób

rm_dup([X], [X]) :- !.
rm_dup([X1, X2 | Xs], Ys) :-
    dif(X1, X2) -> (rm_dup([X2 | Xs], Ys1), Ys = [X1 | Ys1]);
    rm_dup([X2 | Xs], Ys).

Jeszcze lepiej jest po prostu użyć równości jako warunku i odwrócić klauzule then i else .

rm_dup([X], [X]) :- !.
rm_dup([X1, X2 | Xs], Ys) :-
    X1 = X2 ->  rm_dup([X2 | Xs], Ys);
    rm_dup([X2 | Xs], Ys1), Ys = [X1 | Ys1].
a3yko Nov 28 2020 at 03:41

Trochę długo, ale to rozwiązało problem.

delete(_,[],[]).
delete(X,[X|T],R):- delete(X,T,R).
delete(X,[H|T],[H|R]) :- delete(X,T,R).

remove([],[]).
remove([H|T], [H|R]) :- 
    member(H,T),!,
    delete(H,T,R1),
    remove(R1,R).

remove([H|T],[H|R]):-
    remove(T,R).