Equality of sets

Question

Can anyone help me with the following task: I need to define a predicate eq_set, which succeeds if the sets S1 and S2 are equal when it comes to the number of their elements.

But it works only if they are exactly the same number and order. I want to create a code that shows all varieties and doesn't take order into account. Can you help me,please?

I wrote:

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

But it works only if they are exactly the same number and order. I want to create a code that shows all varieties and doesn't take order into account.

The closest translation I have of the assignment, which is in Bulgarian, is: "Define the predicate eq_set, which succeeds if the sets (S1, S2) coincide.

Answer 1

It really really depends on how the predicate is going to be used.

Assuming that a "set" is indeed a Prolog list without duplicates but not in any particular order; then two sets in that presentation "coincide" if they are permutations of each other. In other words, it would be enough to define eq_set/2 as:

eq_set(A, B) :-
    my_permutation(A, B).

and just use the textbook definition of permutation/2 which uses the textbook definition of select/3 (See "The Art of Prolog (Second Edition)" by Sterling and Shapiro, pp 67-9):

my_permutation([], []).
my_permutation(Xs, [Y|Ys]) :-
    my_select(Y, Xs, Xs0),
    my_permutation(Xs0, Ys).

my_select(X, [X|Xs], Xs).
my_select(X, [Y|Ys], [Y|Zs]) :-
    my_select(X, Ys, Zs).

(I renamed those just to make sure I am not using the standard library definitions; SWI-Prolog has both select/3 and permutation/2 in the autoloaded library(lists); the definitions are basically the same, but they do some run-time type-checking on the arguments.)

Here is how you can use it:

?- eq_set([1,2,3], [2,3,1]).
true ;
false.

?- eq_set([1,2,3], S).
S = [1, 2, 3] ;
S = [1, 3, 2] ;
S = [2, 1, 3] ;
S = [2, 3, 1] ;
S = [3, 1, 2] ;
S = [3, 2, 1] ;
false.

?- eq_set([1,2,3], [1,2]).
false.

?- eq_set(A, B).
A = B, B = [] ;
A = B, B = [_4480] ;
A = B, B = [_4480, _4492] ;
...

I am not sure how useful the last query is. You can force it to enumerate solutions in order of increasing size of the "set", like this:

?- length(S1, _), eq_set(S1, S2), numbervars(S1).
S1 = S2, S2 = [] ;
S1 = S2, S2 = [A] ;
S1 = S2, S2 = [A, B] ;
S1 = [A, B],
S2 = [B, A] ;
S1 = S2, S2 = [A, B, C] ;
S1 = [A, B, C],
S2 = [A, C, B] ;
S1 = [A, B, C],
S2 = [B, A, C] ;
S1 = [A, B, C],
S2 = [B, C, A] ;
S1 = [A, B, C],
S2 = [C, A, B] ;
S1 = [A, B, C],
S2 = [C, B, A] ;
S1 = S2, S2 = [A, B, C, D] .

(Don't worry about the numbervars, it is just there to give readable names to all the free variables in the sets. Keep in mind that unifying two free variables makes them the same variable.)

This is a starting point, but maybe it is already good enough. The most glaring omission is that it doesn't require the arguments to be lists without duplicates. One way to define this would be to require that each element is different from all other elements. Since "is different" is commutative, you can define it like this:

is_set([]).
is_set([X|Xs]) :-
    all_different(Xs, X),
    is_set(Xs).

all_different([], _).
all_different([Y|Ys], X) :-
    dif(X, Y),
    all_different(Ys, X).

This uses dif/2 which is a widely available predicate (but does your Prolog have it?).

We would have maybe used maplist for that last one:

is_set([]).
is_set([X|Xs]) :-
    maplist(dif(X), Xs).
    is_set(Xs).