list - repetidos - no repetir resultados en prolog
Eliminar duplicados en la lista(Prolog) (8)
Soy completamente nuevo en Prolog y estoy probando algunos ejercicios. Uno de ellos es:
Escriba un conjunto de predicados (InList, OutList) que toma como entrada una lista arbitraria, y devuelve una lista en la que cada elemento de la lista de entrada aparece solo una vez.
Aquí está mi solución:
member(X,[X|_]).
member(X,[_|T]) :- member(X,T).
set([],[]).
set([H|T],[H|Out]) :-
not(member(H,T)),
set(T,Out).
set([H|T],Out) :-
member(H,T),
set(T,Out).
No tengo permitido usar ninguno de los predicados incorporados (Sería mejor incluso no usar not/1 ). El problema es que ese set/2 da múltiples soluciones iguales . Cuantas más repeticiones en la lista de entrada, más soluciones habrá. ¿Qué estoy haciendo mal? Gracias por adelantado.
Agregando mi respuesta a este viejo hilo:
notmember(_,[]).
notmember(X,[H|T]):-X/=H,notmember(X,T).
set([],[]).
set([H|T],S):-set(T,S),member(H,S).
set([H|T],[H|S]):-set(T,S),not(member(H,S)).
La única virtud de esta solución es que usa solo aquellos predicados que han sido introducidos por el punto donde este ejercicio aparece en el texto original .
Creo que una mejor manera de hacer esto sería:
set([], []).
set([H|T], [H|T1]) :- subtract(T, [H], T2), set(T2, T1).
Entonces, por ejemplo ?- set([1,4,1,1,3,4],S) te da como salida:
S = [1, 4, 3]
Estás en el camino correcto ... Mantente puro , ¡es fácil!
Utilice el predicado de igualdad reificado =/3 (también equal_truth/3 como equal_truth/3 ) en combinación con if_/3 , implementado por @false en la unión de Prolog para AUBUC :
=(X, Y, R) :- X == Y, !, R = true.
=(X, Y, R) :- ?=(X, Y), !, R = false. % syntactically different
=(X, Y, R) :- X /= Y, !, R = false. % semantically different
=(X, Y, R) :- R == true, !, X = Y.
=(X, X, true).
=(X, Y, false) :-
dif(X, Y).
if_(C_1, Then_0, Else_0) :-
call(C_1, Truth),
functor(Truth,_,0), % safety check
( Truth == true -> Then_0 ; Truth == false, Else_0 ).
En base a estos predicados, creamos un predicado de pertenencia reificado list_item_isMember/3 . Es semánticamente equivalente con memberd_truth/3 por @false. Reordenamos el orden de los argumentos, por lo que la lista es el primer argumento. Esto habilita la indexación del primer argumento que evita dejar atrás los puntos de elección inútiles a medida que se memberd_truth/3 .
list_item_isMember([],_,false).
list_item_isMember([X|Xs],E,Truth) :-
if_(E = X, Truth = true, list_item_isMember(Xs,E,Truth)).
list_set([],[]).
list_set([X|Xs],Ys) :-
if_(list_item_isMember(Xs,X), Ys = Ys0, Ys = [X|Ys0]),
list_set(Xs,Ys0).
Una consulta simple muestra que todas las respuestas redundantes se han eliminado y que la meta tiene éxito sin dejar ningún punto de elección detrás :
?- list_set([1,2,3,4,1,2,3,4,1,2,3,1,2,1],Xs). Xs = [4,3,2,1]. % succeeds deterministically
Editar 2015-04-23
Me inspiré en la respuesta de @ Ludwig de set/2 , que dice así:
set([],[]).
set([H|T],[H|T1]) :- subtract(T,[H],T2), set(T2,T1).
El residuo del predicado incorporado de SWI-Prolog subtract/3 puede ser no monótona, lo que puede restringir su uso. list_item_subtracted/3 es una variante monótona de ella:
list_item_subtracted([],_,[]).
list_item_subtracted([A|As],E,Bs1) :-
if_(A = E, Bs = Bs1, Bs1 = [A|Bs]),
list_item_subtracted(As,E,Bs).
list_setB/2 es como set/2 , pero se basa en list_item_subtracted/3 --- not subtract/3 :
list_setB([],[]).
list_setB([X|Xs1],[X|Ys]) :-
list_item_subtracted(Xs1,X,Xs),
list_setB(Xs,Ys).
Las siguientes consultas comparan list_set/2 y list_setB/2 :
?- list_set([1,2,3,4,1,2,3,4,1,2,3,1,2,1], Xs). Xs = [4,3,2,1]. % succeeds deterministically ?- list_setB([1,2,3,4,1,2,3,4,1,2,3,1,2,1],Xs). Xs = [1,2,3,4]. % succeeds deterministically
Uno puede preferir uno u otro, dependiendo del orden deseado de los elementos de la lista en Xs .
Esto funciona sin corte, pero necesita más líneas y otro argumento. Si cambio el [H2 | T2] a S en la línea tres, se producirán resultados múltiples. No entiendo por qué.
setb([],[],_).
setb([H|T],[H|T2],A) :- not(member(H,A)),setb(T,T2,[H|A]).
setb([H|T],[H2|T2],A) :- member(H,A),setb(T,[H2|T2],A).
setb([H|T],[],A) :- member(H,A),setb(T,[],A).
set(L,S) :- setb(L,S,[]).
Solo tienes que detener la vuelta atrás de Prolog.
enter code here
member(X,[X|_]):- !.
member(X,[_|T]) :- member(X,T).
set([],[]).
set([H|T],[H|Out]) :-
not(member(H,T)),
!,
set(T,Out).
set([H|T],Out) :-
member(H,T),
set(T,Out).
Una solución más simple (y probablemente más rápida) es usar el predicado de bibliotecas sort / 2 que elimina los duplicados en O (n log n). Definitivamente funciona en Yap Prolog y SWIPL
Usted está obteniendo múltiples soluciones debido al retroceso de Prolog. Técnicamente, cada solución provista es correcta, y es por eso que se está generando. Si desea que se genere una sola solución, tendrá que detener el rastreo en algún momento. Para esto se usa el corte Prolog. Es posible que leer sobre eso te ayude con este problema.
Actualización: Correcto. Su predicado member() evalúa como true de varias maneras diferentes si la primera variable está en múltiples posiciones en la segunda variable.
He usado el nombre mymember() para este predicado, para no entrar en conflicto con el predicado mymember() de GNU Prolog. Mi base de conocimiento ahora se ve así:
mymember(X,[X|_]).
mymember(X,[_|T]) :- mymember(X,T).
not(A) :- /+ call(A).
set([],[]).
set([H|T],[H|Out]) :-
not(mymember(H,T)),
set(T,Out).
set([H|T],Out) :-
mymember(H,T),
set(T,Out).
Entonces, mi mymember(1, [1, 1, 1]). evalúa como true de tres maneras diferentes:
| ?- mymember(1, [1, 1, 1]).
true ? a
true
true
no
Si quieres tener solo una respuesta, vas a tener que usar un corte. Cambiar la primera definición de mymember() a esto:
mymember(X,[X|_]) :- !.
Resuelve tu problema
Además, puede evitar not() totalidad, si lo desea, definiendo un predicado de notamember() usted mismo. La decisión es tuya.
Utilizando la función de soporte mymember de Tim, puede hacer esto si el orden de los elementos en el conjunto no es importante:
mymember(X,[X|_]).
mymember(X,[_|T]) :- mymember(X,T).
mkset([],[]).
mkset([T|C], S) :- mymember(T,C),!, mkset(C,S).
mkset([T|C], S) :- mkset(C,Z), S=[T|Z].
Entonces, por ejemplo ?- mkset([1,4,1,1,3,4],S) da como resultado:
S = [1, 3, 4]
pero, si quiere un conjunto con los elementos ordenados como en la lista, puede usar:
mkset2([],[], _).
mkset2([T|C], S, D) :- mkset2(C,Z,[T|D]), ((mymember(T,D), S=Z,!) ; S=[T|Z]).
mkset(L, S) :- mkset2(L,S,[]).
Esta solución, con la misma entrada del ejemplo anterior, le brinda:
S = [1, 4, 3]
Esta vez, los elementos están en el mismo orden en que aparecen en la lista de entrada.