"Andrew_Days (sent by Nabble.com)" <lists@xxxxxxxxxx>
asked about
> And I want to know a program write a list who not belongs
> simultaniosly a two lists, and i want to use findall/3.
> For example:
> A=[1,2,3,4,5,6].
> B=[3,4,8,7,6,1].
> L=[2,5,8,7].
No, you DON'T want to use findall/3.
Whyever would you want to do that?
The concept you are after here is "the symmetric difference of two sets".
symdiff(S1, S2) = (S1\S2) U (S2\S1)
where S1\S2 = {X | X in S1 & X not in S2}
I now provide the two forms of set difference in direct (Diff)
and list difference (D0, D) form. They are all O(|S1|.|S2|).
library(sets) in Quintus Prolog provides symdiff/3 (with slightly
different semantics, see below) and setdiff/3 under the name
subtract/3.
% symdiff(+S1, +S2, ?Diff) is true when
% Diff represents the symmetric difference of S1 and S2.
symdiff(S1, S2, Diff) :-
symdiff(S1, S2, Diff, []).
% symdiff(+S1, +S2, ?D0, ?D) is true when
% D0 = symdiff(S1, S2) ++ D
symdiff(S1, S2, D0, D) :-
setdiff(S1, S2, D0, D1),
setdiff(S2, S1, D1, D).
% setdiff(S1, S2, Diff) is true when
% Diff represents the usual set difference S1 \ S2
setdiff(S1, S2, Diff) :-
setdiff(S1, S2, Diff, []).
% setdiff(+S1, +S2, ?D0, ?D) is true when
% D0 = setdiff(S1,S2) ++ D
setdiff([], _, D, D).
setdiff([X|Xs], S, D0, D) :-
( memberchk(X, S) ->
set_diff(Xs, S, D0, D)
; D0 = [X|D1],
setdiff(Xs, S, D1, D)
).
?- A = [1,2,3,4,5,6], B = [3,4,8,7,6,1], symdiff(A, B, L).
=> L = [2, 5, 8, 7]
The question arises: what should happen if either of the lists
contains duplicates? For example, what should
symdiff([1,1], [2,2], Diff)
give as result? The code above will yield
Diff = [1,1,2,2].
Arguably this should be a non-issue, because [1,1] and [2,2] are not
really (representatives of) sets, but of bags or sequences. However,
a small change to setdiff/4 will eliminate duplicates from the answers:
setdiff([], _, D, D).
setdiff([X|Xs], S, D0, D) :-
( memberchk(X, S) ->
set_diff(Xs, S, D0, D)
; D0 = [X|D1],
setdiff(Xs, [X|S], D1, D)
).
With that definition,
symdiff([1,1], [2,2], Diff)
should give the answer
Diff = [1,2]
so the result will represent a set even if the inputs don't.
However, if you use Prolog's "native" representation for sets,
namely ordered lists without duplicates (as returned by sort/2
or setof/3), you can compute all of union, intersection, difference,
and symmetric difference in O(|S1|+|S2|) time, which is such a big
saving in practice that it pays to convert to the "ordered set"
representation using sort/3 for surprisingly small inputs.
Do NOT use findall/3 for operations like this unless you want to
push performance off the top of the Empire State Building. (King King ref...)
|
