Procedure to test whether list represents a set with no duplicates

Question

In Prolog how do you write a procedure that can be used to test whether or not a list represents a set with no duplicates?

score 4 · Accepted Answer · answered Jan 25 '12 at 17:39

There are several ways to do this. @thanosQR is right in pointing to SWI-Prolog's is_set/1, but if you want a portable solution, you can define that predicate in terms of setof:

is_set(Lst) :-
    setof(X, member(X, Lst), Set),
    length(Lst, N),
    length(Set, N).

A list contains no duplicates if its number of elements is equal to the number of elements in the setof its elements.

You can also use the (I believe non-standard, but commonly available) sort/2, which eliminates duplicates:

is_set(Lst) :-
    sort(Lst, Set),
    length(Lst, N),
    length(Set, N).

This takes O(n lg n) time to run.

repeat · Answer 2 · 2019-02-01T19:42:12.843

We define distinct_t/2 based on if_/3 and memberd_t/3:

distinct_t([], true).
distinct_t([X|Xs], T) :-
   if_(memberd_t(X,Xs), T=false, distinct_t(Xs,T)).

Let's start with the most general use of distinct_t/2:

?- distinct_t(Xs,T).
   T = true , Xs = []
;  T = true , Xs = [_A]
;  T = false, Xs = [_A,_A|_B]
;  T = true , Xs = [_A,_B],       dif(_B,_A)
;  T = false, Xs = [_A,_B,_A|_C], dif(_B,_A)
;  T = false, Xs = [_A,_B,_B],    dif(_B,_A), dif(_B,_A)
;  T = true , Xs = [_A,_B,_C],    dif(_B,_A), dif(_C,_A), dif(_C,_B)
...

Alright! How about this quite general query?

?- distinct_t([1,2,X,3],T).
   T = false, X = 1
;  T = false, X = 2
;  T = false, X = 3
;  T = true , dif(X,1), dif(X,2), dif(X,3).

If we are only interested in cases with T = true, we use dictinct/1—defined like this:

distinct(Xs) :-
   distinct_t(Xs, true).

Sample queries:

?- distinct([1,2,3,1]).
false.
?- distinct([1,2,3,2]).
false.
?- distinct([1,2,3,3]).
false.
?- distinct([1,2,3,4]).
true.                     % succeeds deterministically

repeat · Answer 3 · 2019-02-01T19:28:17.937

2

Using sort/2, ground/1, same_length/2, and iwhen/2:

:- use_module(library(lists)).

is_set(S) :-
   iwhen(ground(S), (same_length(S,T), sort(S,T))).

Sample uses:

?- is_set([4,1,3,2]).        % not in standard order
true.                        % OK: no duplicates

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

?- is_set([1,2,3,1,X]).
ERROR: Arguments are not sufficiently instantiated

edited Feb 01 '19 at 19:28

answered Aug 13 '15 at 19:27

repeat

18,496
4
54
166

score 2 · Answer 4 · answered Jan 25 '12 at 17:31

2

First, define a predicate to make sure a value isn't in a list:

notin(A,[]).
notin(A,[B|C]) :- A\=B, notin(A,C).

Then, our nodups predicate makes sure each element doesn't appear in the part of the list that comes after it:

nodups([]).
nodups([_]).
nodups([A|B]) :- notin(A,B), nodups(B).

answered Jan 25 '12 at 17:31

Scott Hunter

48,888
12
60
101

This requires O(n²) time to run. See my answer for an O(n lg n) solution. (Besides, `notin(X,Lst)` can be replaced with `\+ memberchk(X,Lst)`.) – Fred Foo Jan 25 '12 at 17:41
@larsmans why `memberchk/2` instead of `member/2` in a `(\+)/1` call ? It'll stop at the first match anyway, won't it ? – m09 Jan 25 '12 at 17:50
@Mog: I believe `memberchk` is still more efficient; SWI-Prolog's `time/1` shows it performs fewer inferences. – Fred Foo Jan 25 '12 at 18:19

score 1 · Answer 5 · answered Jan 25 '12 at 17:33

1

is_set/1: http://www.swi-prolog.org/pldoc/doc_for?object=is_set/1
(Assuming that you still want it for swi-prolog)

answered Jan 25 '12 at 17:33

Thanos Tintinidis

5,828
1
20
31

score 0 · Answer 6 · answered Jan 25 '12 at 17:45

alternatively, some forall madness (quadratic complexity so it's worse than the is_set/1 mentionned above, but w/e) :

duplicates(List) :-
    forall(select(Item, List, Rest),
           forall(member(Item2, Rest),
                  Item \== Item2)).

Procedure to test whether list represents a set with no duplicates

6 Answers6

Linked