entfernen Wiederholungen mehr als einmal

Question

ich aus einer zuvor geordneten Liste in Prolog mehr als eine Wiederholung entfernen möchte. Ich würde die Ausgabe wie wie folgt aussehen:

Beispiel 1.

?- remove_dups ([1,1,2,2,3,4,5,5,6], List). 
List = [3,4,6] 

Wie Sie sehen können, wäre es nicht eine Wiederholung des gleichen Elements entfernen, aber alles.

habe ich den folgenden Algorithmus, ich einige Änderungen gemacht, aber ohne Erfolg. Hier ist der Algorithmus, den ich verwenden:

remove_dups([], []). 
    remove_dups([X], [X]). 

    remove_dups([X,X|T], [X|R]) :- 
     remove_dups([X|T], [X|R]). 

    remove_dups([X,Y|T], [X|R]) :- 
     X \== Y, 
     remove_dups([Y|T], R). 

    remove_dups([X,Y|T], [X|R]) :- 
     ( X == Y 
     -> remove_dups([Y|T], [X|R]) 
     ; remove_dups([Y|T], R) 
     ). 

jedoch der Ausgang ich mit diesem Algorithmus habe dies.

?- remove_dups([1,1,2,2,3,4,5,5,6], List). 

List = [1,2,3,4,5,6] 

Aber ich würde es wie in Beispiel 1, irgendwelche Tipps zu sein?

Answer 1

Wenn Sie ein Duplikat erkennen, das heißtVereinheitlichung mit [X,X|T], entfernen Sie die restlichen X s aus der Liste:

remove_dups([], []). 
remove_dups([X], [X]). 
remove_dups([X,Y|T], [X|R]) :- 
    X \= Y, 
    remove_dups([Y|T], R). 
remove_dups([X,X|T], R) :- 
    skip(X, T, WithoutX), 
    remove_dups(WithoutX, R). 

Wie Sie sehen können, sind Sie ziemlich nah dran: die Sätze 1, 2 und 3 der remove_dups/2 Regel kam aus dem Code. Der einzige Unterschied besteht in der letzten Klausel, die die verbleibenden Werte von X überspringt, bevor sie rekursiv werden.

skip(_,[],[]). 
skip(X, [X|T], T). 
skip(X, [Y|T], [Y|T]) :- X \= Y. 

Demo.

Answer 2

Das ist ganz ähnlich wie Include non-unique elements only, und kann ziemlich analoguously gelöst werden.

ich wieder if_//3 bin mit Allgemeinheit der Beziehung behalten: Bitte nicht, dass ein nützliches Prolog-Prädikat kann typischerweise in mehr Richtungen verwendet werden, und so ein Imperativ Name wie remove_dups/2 ist nicht geeignet, andere Richtungen auszudrücken und allgemeinere Verwendung   Fälle.

Stattdessen soll ich nennen, die die Beziehung list_singulars/2 und definieren es wie folgt aus:

 
list_singulars(Ls0, Ls) :- 
     phrase(list_singulars(Ls0, []), Ls). 

list_singulars([], _) --> []. 
list_singulars([L|Ls], Ls0) --> 
     if_((memberd_t(L, Ls);memberd_t(L, Ls0)), 
      [], 
      [L]), 
     list_singulars(Ls, [L|Ls0]). 

Hier ist ein einfaches Testfall:

 
?- list_singulars([a,a,b], List). 
List = [b]. 

Und das Beispiel Sie auf dem Laufenden:

 
?- list_singulars([1,1,2,2,3,4,5,5,6], List). 
List = [3, 4, 6]. 

Darüber hinaus können wir auch erzeugen Antworten, eine allgemeine Abfrage:

 
?- list_singulars([a,X], List). 
X = a, 
List = [] ; 
List = [a, X], 
dif(X, a). 

Beachten Sie die Verwendung von dif/2, die eine wahre Beziehung ist. Weitere Informationen finden Sie unter prolog-dif.

Hier ist die allgemeinste query:

 
?- list_singulars(Ls0, Ls). 
Ls0 = Ls, Ls = [] ; 
Ls0 = Ls, Ls = [_6826] ; 
Ls0 = [_6826, _6826], 
Ls = [] ; 
Ls0 = [_6826, _6826, _6826], 
Ls = [] ; 
Ls0 = [_6826, _6826, _6826, _6826], 
Ls = [] . 

Wir können faire Auszählung durch iterative Vertiefung leicht erhalten:

 
?- length(Ls0, _), list_singulars(Ls0, Ls). 
Ls0 = Ls, Ls = [] ; 
Ls0 = Ls, Ls = [_7798] ; 
Ls0 = [_7798, _7798], 
Ls = [] ; 
Ls0 = Ls, Ls = [_8436, _8442], 
dif(_8442, _8436) ; 
Ls0 = [_7798, _7798, _7798], 
Ls = [] ; 
Ls0 = [_8494, _8494, _8506], 
Ls = [_8506], 
dif(_8506, _8494) .