Check if all numbers in a list are different in prolog

Question

I want to create a rule in prolog that checks if there's a repeated number in a list.

For example:

• for [1,2,3,4] it will return true.
• for [1,2,3,3] it will return false because the 3 is repeated

I came up with this rule but it doesn't work

Different([]).
Different([H|T]):-
     Member(H,T),
     Different(T).

Any ideas?

Answer 1

a compact definition could be

all_diff(L) :- \+ (select(X,L,R), memberchk(X,R)).

i.e. all elements are different if we can't peek one and find it in the rest...

edit

Let's (marginally) improve efficiency: it's useless to check if X is member of the prefix sublist, so:

all_diff(L) :- \+ (append(_,[X|R],L), memberchk(X,R)).

Answer 2

The simplest way to check that all list members are unique is to sort list and check that length of the sorted list is equal of length of the original list.

different(X) :-
    sort(X, Sorted),
    length(X, OriginalLength),
    length(Sorted, SortedLength),
    OriginalLength == SortedLength.

Your solution doesn't work because of wrong syntax (facts and predicates should not begin with a capital letter) and a logic error. List is unique if head H is not a member of a tail T of a list and tail T is unique:

different([]).
different([H|T]):-
    \+member(H,T),
    different(T).

Answer 3

If all numbers in that list are integers, and if your Prolog implementation offers clpfd, there's no need to write new predicates of your own---simply use the predefined predicate all_different/1!

:- use_module(library(clpfd)).

Sample use:

?- all_different([1,2,3,4]).
true.

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

Answer 4

Very Simple Answer...

The code:

unique([]). unique([_,[]]). unique([H|T]):-not(member(H,T)),unique(T).

Tests:

?-unique([1,2,3,4]). true. ?-unique([1,2,3,3]). false. ?-unique([a,b,12,d]). true ?-unique([a,b,a]). false

Answer 5

A neat way I came up with is the following:

If all members of a list are different from each other, then if I tell prolog to choose all pairs (I,J) such that I,J are members of the list and also I is equal to J, then for each element in the list it will only be able to find one such pair, which is the element with itself.

Therefore, if we can put all such pairs in a list, then the length of this list should be of the same length of the original list.

Here's my prolog code:

all_diff(L) :-
        findall((I,J), (member(I, L), member(J, L), I == J), List),
        length(L, SupposedLength),
        length(List, CheckThis),
        SupposedLength == CheckThis.

Answer 6

The rule provided in the question is very close to a correct answer with minimal library usage. Here's a working version that required only one change, the addition of \+ in the third row:

uniqueList([]).
uniqueList([H|T]):-
     \+(member(H,T)),
     uniqueList(T).

Explanation of the code for Prolog beginners: The member(H,L) predicate checks if element H is a member of the list L. \+ is Prolog's negation function, so the above code amounts to:

uniqueList([H|T]) returns true if: (H doesn't have a copy in T) and uniqueList(T)

Whereas the code by the original asker didn't work because it amounted to:

uniqueList([H|T]) returns true if: (H has a copy in T) and uniqueList(T)

*I renamed Different() to uniqueList() because it reads better. Convention is to reserve capital letters for variables.

Answer 7

This isn't very efficient, but for each number you can check if it appears again later. Like so:

Different([H|T]):-
  CheckSingle(H, [T]),
  Different([T]).

Checksingle(_,[]).

Checksingle(Elem, [H, T]):-
  Elem != H,
  Checksingle(Elem, [T]).