Programa Prolog para encontrar la igualdad de dos listas en cualquier orden

Question

Quería escribir un programa Prolog para encontrar la igualdad de dos listas, donde el orden de los elementos
no importa. Así que escribí lo siguiente:

del(_, [], []) . 
del(X, [X|T], T). 
del(X, [H|T], [H|T1]) :- 
    X \= H, 
    del(X, T, T1). 

member(X, [X|_]). 
member(X, [_|T]) :- 
    member(X, T). 

equal([], []). 
equal([X], [X]). 
equal([H1|T], L2) :- 
    member(H1, L2), 
    del(H1, L2, L3), 
    equal(T, L3). 

Pero cuando le doy de entrada como equal([1,2,3],X)., que no muestra todos los valores posibles de X. En cambio, el programa se cuelga en el medio. ¿Cuál podría ser la razón?

Answer 1

isSubset([],_). 
isSubset([H|T],Y):- 
    member(H,Y), 
    select(H,Y,Z), 
    isSubset(T,Z). 
equal(X,Y):- 
    isSubset(X,Y), 
    isSubset(Y,X). 

Answer 2

Prueba esto:

equal([],[]). 
equal([Ha|Ta],[Hb|Tb]) :- 
    Ha = Hb, lequal(Ta,Tb). 

Answer 3

Trate de usar predicado que comprueba si uno de los conjuntos es una permutación de otro conjunto:

delete(X, [X|T], T). 

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


permutation([], []). 

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

(Predicados tomado de http://www.dreamincode.net/code/snippet3411.htm)

?- permutation([1,2,3],[3,1,2]). 
true 

Answer 4

Sugiero usar el built-in p redicate msort/2, luego comparando las listas. Toma tiempo O (nlogn) en SWI Prolog, mientras que el control de listas sin clasificar ingenuamente elemento por elemento tomaría O (n) vez.

lists_equal(List1, List2) :- 
    msort(List1, Sorted1), 
    msort(List2, Sorted2), 
    Sorted1=Sorted2. 

Aquí, ordenar listas toma tiempo O (nlogn), y compararlos toma tiempo O (n) en SWI Prolog, no sé acerca de otras implementaciones.

Answer 5

Brevemente

equal([],[]). 
equal([H|T],[H|T1]):-equal(T,T1). 

Answer 6

¿Qué tal:

equal(X, Y) :- 
    subtract(X, Y, []), 
    subtract(Y, X, []). 

Answer 7

Si no se preocupan por las multiplicidades de los elementos de la lista y sólo utiliza el predicado con la suficiente creación de instancias, considerar hacerlo de esta manera:

same_elements(As,Bs) :- 
    ( ground(As+Bs) 
    -> maplist(sort, [As,Bs], [Es,Es])  % same as `sort(As,Es), sort(Bs,Es)` 
    ; throw(error(instantiation_error,_)) 
    ). 

Answer 8

El motivo real de la no terminación que usted observa ed es esto: la siguiente cláusula no restringe L2 de ninguna manera, forma o forma.

 
equal([H1|T], L2) :- 
    member(H1, L2), 
    del(H1, L2, L3), 
    equal(T, L3). 

Por lo que su consulta ?- equal([1,2,3], X). implica que demuestra el objetivo member(_, L2) que no pongan fin universalmente. ¡Por lo tanto, equal([1,2,3], X) no puede terminar universalmente también!

Para obtener más información sobre cómo explicar no terminación de código Prolog leer sobre failure-slice!

---

PS. En cuanto a la terminación problema desde un ángulo diferente, vemos que la terminación no es, de hecho, una consecuencia necesaria en este caso.

¿Por qué? Porque no restringe el número de multiplicidades, lo que hace que la solución tenga un tamaño infinito. El conjunto no puede ser representado por un número finito de respuestas (siempre que no permita retrasar los objetivos).

Answer 9

¿Por qué el equal([1,2,3], X) no termina de forma universal con su código?

¡Echemos un vistazo a failure-slice de su código! ¿Qué son las rebanadas de falla? Aquí está la información de la etiqueta:

A failure-slice is a fragment of a Prolog program obtained by adding some goals false . Failure-slices help to localize reasons for universal non-termination of a pure monotonic Prolog program. They also help to give a lower bound for the number of inferences needed. It is a concrete program-slicing technique.

Para crear una rebanada fracaso:

• insertamos false objetivos en el programa
• mientras se asegura de que el fragmento no termina con el objetivo anteriormente.

 
del(_, [], []) :- false. 
del(X, [X|T], T) :- false. 
del(X, [H|T], [H|T1]) :- false, 
    dif(X, H),     % note that the OP originally used `X \= H` 
    del(X, T, T1). 

member(X, [X|_]). 
member(X, [_|T]) :- 
    member(X, T). 

equal([], []) :- false. 
equal([X], [X]) :- false. 
equal([H1|T], L2) :- 
    member(H1, L2), false, 
    del(H1, L2, L3), 
    equal(T, L3). 

?- equal([1,2,3], _), false.  % note that `false` is redundant ... 
** LOOPS **      % ... as above `equal/2` cannot succeed. 

Así que ... lo que hace por encima de la rebanada fracaso decirnos? Dice:

• Para que el objetivo equal([1,2,3], X) terminar universalmente ...
• ... tenemos que cambiar al menos una de las partes restantes (los que no tachado a través)!