Prolog program for finding equality of two lists in any order

Question

I wanted to write a Prolog program to find the equality of two lists, where the order of the elements doesn't matter. So I wrote the following:

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). 

But when I give input like equal([1,2,3],X). , it does not display all possible values ​​of X Instead, the program freezes in the middle. What could be the reason?

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

Try using a predicate that checks if one of the sets is a permutation of the other set:

 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). 

(Predicate taken from http://www.dreamincode.net/code/snippet3411.htm )

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

Answer 3

The actual reason you are not being treated is this: the following sentence does not limit L2 any way, form or form.

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

So your query ?- equal([1,2,3], X). implies proof of the purpose of member(_, L2) , which does not stop everywhere. Therefore, equal([1,2,3], X) also cannot stop!

For more information on how to explain rejection of prolog code, read failure-slice !

---

PS. Considering the problem of termination from a different angle, we see that in this case, insuperability is a necessary consequence.

Why? Because you do not limit the number of multiplicities, which makes the solution infinite in size. A set cannot be represented by a finite number of answers (provided that you do not allow to delay goals).

Answer 4

If you don’t care about the multiplicity of the list items, check for a sufficient number of instances using ground/1 , apply it with iwhen/2 and remove duplicates with sort/2 as follows:

 same_elements(As, Bs) :- iwhen(ground(As+Bs), (sort(As,Es),sort(Bs,Es))). 

Example usage with SWI Prolog 8.0.0:

  ? - same_elements ([a, c, c, b, a, c], [c, b, b, a]).
 true

 ? - same_elements ([a, b, b, a], [b, a, b, e]).
 false

 ? - same_elements ([a, b, b, a], Xs).
 ERROR: Arguments are not sufficiently instantiated

Answer 5

Try the following:

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

Answer 6

What about:

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

Answer 7

So why does equal([1,2,3], X) not end up universally with your code?

Look at your failure-slice code! What are failures? Here is the tag information:

Failure Failure - A fragment of the Prolog program obtained by adding multiple targets to false . Fail-safe fragments help to localize the reasons for the universal failure of a pure monotonous Prolog program. They also help to give a lower estimate of the number of conclusions needed. This is a specific program-slicing .

To create a slice of failure:

• we insert false targets into the program
• making sure that the fragment does not end with the above value.

  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.

So ... what does refusal of refusal mean? It says:

• So that the goal equal([1,2,3], X) ends universally ...
• ... we must change at least one of the remaining parts (those that are not crossed out )!

Answer 8

I suggest using msort/2 built-in predicate and then compare lists. It takes O (nlogn) time on the SWI Prolog, while checking unsorted lists naively by elements will take O (n ² ).

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

Here, sort lists take O (nlogn) time, and comparing them takes O (n) time in SWI Prolog, I don't know about other implementations.

Answer 9

Short

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