Prolog: Sets and operations

Question

I'm developing predicates in prolog to manipulate sets. I'm trying to implement 3 predicates, using the following in-built predictes: member/2, append/3, length/2, permutation/2:

1) list_to_set/2

A predicate that convert a list in to a set. Given the list Xs = [1, 2, 3, 3] I need to return the permutation of Xs with no duplicates.

INPUT

?- list_to_set([3, 1, a, a], Es).

OUTPUT

?- Es = [1,3,a];
?- Es = [1,a,3];
?- Es = [3,1,a];
?- Es = [3,a,1];
?- Es = [a,1,3];
?- Es = [a,3,1].

2) Union/3

Given two sets Xs, Rs. the predicate Union(Xs, Rs, Es) checks if Es is the union between set Xs and Rs.

INPUT

?- union([2,1,3,a], [4,1,3,a], Es).

OUTPUT

?- Es = [1,3,a];
?- Es = [1,a,3];
?- Es = [3,1,a];
?- Es = [3,a,1];
?- Es = [a,1,3];
?- Es = [a,3,1].

4) diff/3

Given two sets Xs, Rs. the predicate Diff(Xs, Rs, Es) checks if Es is the difference between set Xs and Rs.

INPUT

?- diff([2,1,3,a], [4,1,3,a], Es).

OUTPUT

?- Es = [2, 4];
?- Es = [4, 2].

Here's what I've done so far:

%list to set predicate
list_to_set(Xs , Cs) :-
  lpc(Xs, [], Cs).

lpc([], Rs, Rs).
lpc([X | Xs], Rs, Cs):-
    member(X, Rs),
    lpc(Xs, Rs, Cs).
lpc([X | Xs], Rs, Cs):-
    lpc(Xs, [X|Rs], Cs).

%union between two sets predicate
union([], _, _).
union([C|Cs], Ds, Es) :-
    member(C, Ds),
    union(Cs, Ds, Es).
union([C|Cs], Ds, [C|Es]) :-
    member(C, permutation(Cs, Es)),
    union(Cs, Ds, Es).

diff([], _, []).
diff([C |Cs], Ds, Es):-
    member(C, Ds),
    diff(Cs, Ds, Es).
diff([C | Cs], Ds, [C | Es]):-
    member(C, permutation(Cs, Es)),
    diff(Cs, Ds, Es).

Guys, How can I adapt the code above to work with permutations? I've tried various implementations but none of them works.

Without looking at your implementation, but simply inspecting the query union([2,1,3,a], [4,1,3,a], Es).: You have here all 3! permutations for Es. That will not extend easily to larger sets. You will have to introduce functional dependencies thereby reducing those n! solutions to a single one. — false

SierraV SierraV · Accepted Answer · 2020-06-26T06:21:15

List to set

 list_to_set([], []).

 list_to_set([H|T], Z):-
     member(H,T),
     list_to_set(T, Z1),!,
     permutation(Z1,Z).

 list_to_set([H|T], Z):-
     not(member(H,T)),
     list_to_set(T, Z1),!,
     append([H], Z1, Z2),
     permutation(Z2,Z).

    union([],_,[]).
    union([H|T], L2, Es):-
        union(T, L2, Z1),
        (member(H, L2) -> append([H],Z1,Z2) ; Z2 = Z1),!,
        list_to_set(Z2, Es).

    diff(L1, L2, Es):-
        append(L1,L2,L3),
        union(L1,L2,L4),!,
        subtract(L3,L4,L5),
        list_to_set(L5,Es).

If you can't use the subtract predicate, it is not difficult define your own implementation.

Prolog: Sets and operations

1 Answers