Set Difference of Two Compatible Lists

Help! Algorithm
1

Hey guys, I posted a question here about a week ago on the same topic and I can appreciate the question was quite unspecific ( I had no clue what I was doing at the time ). But now I’ve come some way and need help with a problem which I hope more of you could help with.

I’m currently trying to implement an automated theorem prover in prolog and have stumbled across a problem.

If I have a list of lists such as: [[1,2],[-1,3],[4,5,7],[-2,4]]

How would I get the “set difference” of two compatible list items: What I mean by compatible is, if the negation of a certain number exists in another list, then replace those two lists with the set difference, ie: [1,2] and [-1,3] are compatible because -1 is present in the second clause and thus it should return the set difference of [2,3] and the new list should be [[2,3],[4,5,7],[-2,4]].

Currently I have this following step:

memberlist(X,[[X|_]|_]).
memberlist(X,[[_|T1]|T2]) :-
    memberlist(X,[T1|T2]).
memberlist(X,[[]|T2]) :-
    memberlist(X,T2).

step([]).
step([_|T]) :-
    memberlist(neg X,T),
    write(X),
    nl,
    step(T).
step([_|T]) :-
    step(T).

So it simply checks each list and checks if the negation of a variable exists and if it does simply write it out. I’ve already added code which deals with negative number - so neg X will match to -X (x being any integer).

I’m quite stuck at this point, and any help would be greatly appreciated.

2

i don’t think I understand this …

Can you clarify a bit more abstractly what the meaning of compatible and set difference is:

Say, given two (“composite”) elements in list such as [[X1,Y1], [X2,Y2]], what is the condition for compatibility and set difference – in terms of X1, Y1, X2, and Y2.

Perhaps write a predicate by way of explanation such as below, where X, Y represents the result of the determination.

compatible_item(X1, Y1, X2, Y2, X, Y) :-

thanks,

Dan

3

select/3 often is useful to simplify non deterministic code. Here is used for both matching of elements and sets. diff_compatible_all/2 will run until there are compatible sets.

diff_compatible(S1,S2,S) :-
    select(E1,S1,R1),
    select(E2,S2,R2),
    compatible(E1,E2),
    append([R1,R2],S).

compatible(X,Y) :- X =:= -Y ; -X =:= Y.

diff_compatible_all(S0,D) :-
    select(S1,S0,R1),
    select(S2,R1,RA),
    diff_compatible(S1,S2,S),
    !,
    diff_compatible_all([S|RA],D).
diff_compatible_all(D,D).

:- begin_tests(dcl).

test(1) :-
    diff_compatible_all([[1,2],[-1,3],[4,5,7],[-2,4]],[[3,4],[4,5,7]]).
test(2) :-
    diff_compatible([1,2],[-1,3],[2,3]).

:- end_tests(dcl).

Running…

?- run_tests.
% PL-Unit: dcl .
Warning: .../dcl.pl:21:
	PL-Unit: Test 2: Test succeeded with choicepoint
 done
% All 2 tests passed
true.
2 Likes
4

This is cross posted on StackOverlfow.

5

Sorry about that, I’ll happily clarify for you.
So with the example [[X1, Y1], [X2, Y2]], the clauses would be compatible if the negation of X1 or Y1 were equal to X2 and Y2…let me try make it a bit more formal:
[X1, Y1] would be compatible with [X2, Y2] if (X2 = neg(X1) OR neg(Y1) OR Y2 = neg(X1) or neg(Y1))

In the instance two set are compatible, then simply remove the variable and it’s negation that you matched with and add then merge the two clauses. So if X2 was equal to neg X1, then the set difference would be [[Y1, Y2]].

So going back to my original example, if I have: [[1,2],[-1,3],[4,5,7],[-2,4]]
[1,2] and [-1,3] are compatible so we should have [[2,3],[4,5,7],[-2,4]]
Now [2,3] and [-2,4] are compatible so we should now have [[3,4],[4,5,7]]

Now there are no more possible compatible sets, so return [[3,4],[4,5,7]] as the final result.

I hope that explained it a bit better :).