CODEWITHSUNDEEP
listprologsetpermutation
Occhima
Occhima

Reputation: 253

Prolog: Sets and operations

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.

Upvotes: 0

Views: 322

Answers (1)

SierraV
SierraV

Reputation: 104

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

2) Union

WARNING: This is not the set union operation, it's more like the intersection (the code is based on your example). 
    union([],_,[]).
    union([H|T], L2, Es):-
        union(T, L2, Z1),
        (member(H, L2) -> append([H],Z1,Z2) ; Z2 = Z1),!,
        list_to_set(Z2, Es).

3) Diff
WARNING: this is not the set difference operation, it's more like the symmetric difference (again, the code is based in your example). 
    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.

Upvotes: 1

Related Questions