Comment supprimer les doublons d'une liste en SWI-Prolog?

Donc j'ai besoin d'écrire un prédicat remove_duplicates/2 qui supprime les éléments en double forme d'une liste donnée. Par exemple:

?- remove_duplicates([a,a,b,c,c], List). List = [a,b,c] Yes

Veuillez garder à l'esprit que je suis en train d'apprendre SWI-Prolog pour deux jours et seulement comprendre les principes de base de Prolog. C'est ce que j'ai en ce moment:

remove_duplicates([H | T], List) :- member(H, T), append(T, [], List1).

Cela fonctionne pour la liste [a,a,b,c] mais pas pour des listes où les deux éléments de la queue sont les mêmes. J'ai pensé que j'ai en quelque sorte pour retirer la Tête d'une liste temporaire, de créer une nouvelle Tête et il suffit de répéter le prédicat. Je n'ai aucune idée de comment faire cela. Aussi, lorsque la Tête n'est pas dans la Queue, par exemple avec des listes de ce genre [a,b,b,c,], le terminal juste dit False, parce que member(H, T) n'est pas vrai.

Des idées?

Double Possible de Supprimer les doublons dans la liste (Prolog)
Il y a beaucoup de semblables questions et réponses sur l' [prologue] tag, toutefois, je ne suis pas sûr si le projet (et acceptées) les solutions sont nécessairement que les grands. Je ne prétends pas que ma réponse ci-dessous est mieux, mais au moins ça montre une approche différente.
Vous avez raison, il y a beaucoup de impures des solutions à ce problème. J'ai pris la question " d'où au moins une solution (celle de @repeat), a travaillé pour les non-rez-de-termes. Je considère votre solution mieux adaptée pour les débutants, car il ne repose pas sur la réification.

OriginalL'auteur Marthijn | 2016-09-11

prolog

8

De supprimer les doublons, si l'ordre n'a pas d'importance, le plus simple est d'utiliser sort/2:
```
?- sort([a,a,b,b,c], X).
X = [a, b, c].

?- sort([c,c,a,a,b], X).
X = [a, b, c].
```
Bien sûr, vous voyez qu'à l'origine, l'ordre des éléments est perdu. Plus important encore, cela ne garantit correcte si la liste de tri est déjà au sol (pas de variables libres). Considérons cet exemple:
```
?- sort([X,Y], [a,a]).
X = Y, Y = a.
```
Ne se sent pas exactement si votre objectif est de supprimer les doublons....

De sorte que vous pourriez aussi bien avoir écrit:
```
must_be(ground, List), sort(List, Unique).
```
Vous pouvez aussi le faire vous-même, et de conserver l'original de l'ordre. Mais ensuite, vous avez besoin de garder une trace des éléments que vous avez vu jusqu'à présent. Par exemple, vous pouvez les conserver dans une liste:

La liste de l'élément vu jusqu'à présent est vide au début
```
list_unique(List, Unique) :-
    list_unique_1(List, [], Us).

list_unique_1([], _, []).
list_unique_1([X|Xs], So_far, Us) :-
    list_unique_2(X, Xs, So_far, Us).
```
Si tous les éléments vus jusqu'à présent sont différents de X,
le mettre dans la liste des éléments uniques et l'ajouter à la
liste des éléments vus jusqu'à présent.
```
list_unique_2(X, Xs, So_far, [X|Us]) :-
    maplist(dif(X), So_far),
    list_unique_1(Xs, [X|So_far], Us).
```
Si l'élément a été vu jusqu'à présent, il suffit de sauter.
```
list_unique_2(X, Xs, So_far, Us) :-
    memberchk(X, So_far),
    list_unique_1(Xs, So_far, Us).
```
C'est la plus simple façon de le faire. Il y a d'autres plus malin des façons de faire qui pourraient avoir une meilleure complexité, mais c'est le plus facile à écrire.

Ce sujet de la requête sort([a,X,b,X],L), X=b.? Il en résulte L = [b, a, b] qui je suppose qu'il est indésirable.
Yep, même ceci: sort([X,Y], [a,a]) montre le même problème. Le tri n'est pas une opération logique, et sa sémantique est: "trier la liste dans le premier argument de la fonction de commande standard de termes et d'unifier le résultat avec le deuxième argument". Vous pouvez voir cette question et les réponses pour plus d'exemples. Corrigé ma réponse.

OriginalL'auteur
3

Le sont quelques-uns des problèmes avec votre prédicat:
```
remove_duplicates([H | T], List) :-
  member(H, T),
  append(T, [], List1).
```
D'abord, vous devez avoir un prédicat récursif ,vous vérifiez la tête de la liste, mais que vous n'avez pas de manière récursive vérifier la queue de la liste:

de sorte que vous pouvez le changer à:
```
remove_duplicates([H | T], List) :- 
      member(H, T),
      remove_duplicates( T, List).
```
Ci-dessus appelle récursivement pour la queue.

Deuxième, vous devez décider ce qui se passe si h n'est pas membre de la liste de sorte que vous devez ajouter un autre article :
```
remove_duplicates([H | T], [H|T1]) :- 
       \+member(H, T), 
       remove_duplicates( T, T1).
```
Les vérifications ci-dessus si H existe dans T et si pas de forces le premier élément de la liste que vous souhaitez revenir à l'élément H:

si ce n'est pas si clair, le ci-dessus est égale à ceci:
```
  remove_duplicates([H | T], List) :- 
           \+member(H, T), 
           List=[Head|Tail],
           Head=H,
           remove_duplicates( T, Tail).
```
Ce n'est pas très élégant ,c'est juste pour comprendre comment les œuvres précédentes.

Dernier vous besoin d'une base pour votre récursivité pour la liste vide:
```
remove_duplicates([],[]).
```
Donc le prédicat remove_duplicates selon les paragraphes ci-dessus doit être:
```
remove_duplicates([],[]).

remove_duplicates([H | T], List) :-    
     member(H, T),
     remove_duplicates( T, List).

remove_duplicates([H | T], [H|T1]) :- 
      \+member(H, T),
      remove_duplicates( T, T1).
```
Si vous avez remarqué que le ci-dessus ne conserver qu'une seule fois chaque élément, par exemple:
```
remove_duplicates([a,a,b,c],L).
L = [a, b, c] ;
false.
```
C'est ok, mais vérifiez l'exemple ci-dessous :
```
remove_duplicates([a,a,b,a,c],L).
L = [b, a, c] ;
L = [b, a, c] ;
false.
```
Ce sera le retour de L=[b,a,c] parce qu'il a effacé les deux premier " a " de la liste et gardé seulement le troisième.

Si vous souhaitez effacer uniquement les doublons ci-dessus ne fonctionnera pas en raison de membre de prédicat.
Vous pourriez écrire :
```
remove_duplicates2([],[]).

remove_duplicates2([H],[H]).

remove_duplicates2([H ,H| T], List) :-remove_duplicates( [H|T], List).

remove_duplicates2([H,Y | T], [H|T1]):- Y \= H,remove_duplicates( [Y|T], T1).
```
Le prédicat remove_duplicates2 est similaire à remove_duplicates mais avec quelques différences importantes:

1)Vous n'utilisez pas membre, mais vous examinez ce qui se passe quand vous avez une liste [H,H|T] avec les deux MÊMES éléments et en garder qu'un, donc vous ignorez le premier H et appeler récursivement remove_duplicates2([H|T],L).

2)Si vous avez d'entrée [H,Y|T] (une liste d'au moins deux éléments de H,Y et une queue de liste) et H\=Y vous appelez remove_duplicates2([Y|L],T1) et que vous avez stockés H à la Liste que vous souhaitez retourner.

3) Enfin, parce que tous les de la clause du besoin d'au moins deux éléments de base de la récursivité est la liste avec un seul élément : remove_duplicates2([H],[H]).

4) La clause remove_duplicates2([],[]). n'est utilisé que si l'entrée est la liste vide ,de sorte qu'il est nécessaire pour couvrir cette entrée.

La remove_duplicates2 prédicat vous donnerait :
```
 remove_duplicates2([a,a,b,a,c],L).
L = [a, b, a, c] ;
false.

remove_duplicates2([a,a,b,c],L).
L = [a, b, c] ;
false.
```
OriginalL'auteur coder
0

Vous pouvez utiliser list_to_set/2 ou sort/2 comme dit dans la réponse ici.

OriginalL'auteur Anton Danilov
0
```
% remdup(List, List_No_duplicates).
remdup([],[]).
remdup([H|T],Lnd):- rd1(H,T,T1), remdup(T1,Tnd),Lnd=[H|Tnd].
% rd1(X,L,Lr) removes all occurance of X in List L and store result in List Lr
rd1(_,[],[]).    
rd1(X,[X|T],Lx):-    rd1(X,T,Lx).
rd1(X,[Y|T],Lx):-    rd1(X,T,Lx1),Lx=[Y|Lx1].
```
La façon dont il fonctionne prédicat remdup
1. Prendre la 1ère de l'élément H de la Liste et supprimer toutes les occurrences de la Queue T - stocker le résultat dans la Liste de T1; ET
2. Appel remdup de manière récursive sur T1 stocker le résultat dans une Tnd; ET
3. Ajouter l'élément H de Td qui est en fait la Queue, T a été modifié par l'appel récursif de remdup et est donc déjà libre de tous les doublons et ne contient aucune occurrence de H.
prédicat - rd1
1. Suppression de tous les événements et n'importe quoi à partir d'une liste vide est une liste vide
2. Si la tête correspond à X - continue à appeler de nouveau sur la Queue
3. si la tête ne marche pas de match X - continuer ensuite à la queue; ET ajouter inégalée tête Y à la modification de la queue, qui est maintenant libre de toutes les occurrences de X
OriginalL'auteur Nelson aka SpOOKY
0

Essayer, j'espère que ça va vous aider à:
```
delete3(_,[],[]).
delete3(X,[X|T],R):- delete3(X,T,R).
delete3(X,[H|T],[H|R]) :- delete3(X,T,R).

remove_duplicates([],[]).
remove_duplicates([H|T], [H|R]) :- 
    member(H,T),!,
    delete3(H,T,R1),
    remove_duplicates(R1,R).

remove_duplicates([H|T],[H|R]):-
    remove_duplicates(T,R).
```
Dans le second prédicat, nous vérifions si la tête de la variable*(H)* est membre de la queue de la liste*(T)*. Si c'est pour nous l'appelons le premier prédicat qui supprime toutes les variables égales à la tête de la variable qui sont dans la queue, et ainsi de suite.

OriginalL'auteur Sara Popa

Vous devez vous connecter pour publier un commentaire.