# How do you check if there are any equal arguments(even sublist) in a list?

I would like to set up a function which has to return True if at least two arguments of a given List are equal.

So if I give {1,4,6,2} to the function it has to return False (since none of his arguments are equal) and the same would happen if I gave {{1,2,3},{2,3,4}}, while if I gave {1,2,3,1,4} or {{1,2,3},{2,0,0},{1,2,3},{2,1,2}} it has to return True.

I know this is a very simple problem and i think you can easily tell me a convenient way to achieve that.

If there are repeated elements in the list, then calling Union[] on it will shorten it so that this element only appears once, so a simple implementation would be to test these lengths:

 test[list_] := Length[Union[list]] != Length[list]


If you wanted to know which elements where repeated, you this could be accomplished by using Gather[] to collect identical elements, and picking out which groups have more then one element.

 repeats[list_] := Select[Gather[list], Length[#] > 1 &][[1 ;;, 1]]


Note, I'm using Union rather then DeleteDuplicates[] since (as Mr. Wizard corrected me) it is faster. I can't say why except that DeleteDuplicates[] retains the order of elements which may require slightly more bookkeeping. And in this case we don't care about the book keeping. Naturally if you really needed something really speedy, a better solution exists which doesn't search through the entire list, but stops if just a single duplicate is found, Mr. Wizards Answer is just such an function, since Signature exits early if duplicates exist, though it becomes slower if no duplicates are present, it's a trade off.

• This is really great,jVincent and it totally wprks! Anyway i was wondering if you could save information about the argument repeated:i mean from your approach i can't tell which was the argument repeated,isn't it? Anyway,thanks again. Jun 13, 2012 at 8:41
• Any reason why you prefer Union over DeleteDuplicates? Jun 13, 2012 at 12:10
• @Ajasja Not really, I just use Union to join list far more often then I use DeleteDuplicates, and knew that it removes duplicates when called with only one list, so it was the first function to come to mind. Though just running a couple of Timing's I see that union is slightly slower, so I'm updating my answer. Thank you for the question. Jun 13, 2012 at 12:49
• You might want to restore this to Union. Compare these timings: a = RandomInteger[10, {100000, 50}]; then Timing[Union@a;] and Timing[DeleteDuplicates@a;] Jun 13, 2012 at 14:29
• @Mr.Wizard I did almost the exact same test and found DeleteDuplicates to be the faster one, though running this again, Union wins out. I think I might have just misread which line was which. Jun 13, 2012 at 17:44

As it happens there is a built-in function that already does this: Signature.

If any two elements of list are the same, Signature[list] gives 0.

dupeQ = 0 === Signature@# &;


I believe this is the "canonical" answer. It is fast on both packed arrays and unpacked lists.

• +1 for Signature which has been there since v1 but which I've never noticed. Your claim of speed, though, is incorrect. It's only true for lists that actually contain a duplicate. Try l = RandomInteger[100000, {1000000, 3}]; and your dupeQ is almost 10 times slower than kguler's duplicatesQ. I vote against this being a canonical answer. Jun 13, 2012 at 12:51
• There's more. It's very critically dependent on the dimensions of the test array. Use this one l = RandomInteger[10, {1000000, 50}]; and the timings are totally different. duplicatesQ totally can't handle this and yours is extremely much faster. It takes 5 secs for yours and duplicatesQ is still running for a couple of minutes without finishing. Interesting behaviour... Jun 13, 2012 at 13:04
• So, perhaps canonical after all. Jun 13, 2012 at 13:15
• @Sjoerd I honestly wish that were an option; as I think you know I would like to see a collaborative-answer feature added. Jun 13, 2012 at 13:28
• @Mr.Wizard Of cause, I included the seed for the random numbers to allow for direct comparison. But lets be fair here, If we have a = Range[1*^7]; a[[{1, 50}]] = 3.14159; and b = Range[1*^7]; a[[{1, 1*^6}]] = 3.14159; Then on my Machine dupeQ wins on a with 0.063 against 0.984 for test and test wins b with 1.891 vs. 2.344 for dupeQ. To sum up, if there are duplicates then dupeQ wins because it can exit early, and if there are not any duplicates Union wins, most likely because Signatur has to suddenly figure out the actual signature, though oddly still slower if the duplicate is at the end Jun 13, 2012 at 18:16
duplicatesQ = # != DeleteDuplicates[#] &


Usage:

duplicatesQ[{1, 4, 6, 1}]
(* ===> True   *)
duplicatesQ@{1, 4, 6, 2}
(* ==> False *)
duplicatesQ@{{1, 2, 3}, {2, 0, 0}, {1, 2, 3}, {2, 1, 2}}
(* ==> True  *)
duplicatesQ /@ {{1, 2, 3}, {2, 0, 0}, {1, 2, 3}, {2, 1, 2}}
(* ==> {False, True, False, True} )


or (to also get the duplicate elements and their count when there are duplicate elements)

dups = (Select[Tally[#], Last[#] > 1 &] /. {} -> "None") &


Usage:

dups /@ {{1, 2, 3}, {2, 0, 0}, {1, 2, 3}, {2, 1, 2}}
(* ==> {"None", {{0, 2}}, "None", {{2, 2}}}  *)
dups[{{1, 2, 3}, {2, 0, 0}, {1, 2, 3}, {2, 1, 2}}]
(* ==> {{{1, 2, 3}, 2}}  *)


You could also let the pattern matcher do all the work:

DuplicatesQ[l_] := MatchQ[l, {___,x_,___,x_,___}]


Or:

DuplicatesQ[{___,x_,___,x_,___}] := True
DuplicatesQ[_] := False

• +1 for elegance, but be warned this is quite slow. Jun 13, 2012 at 11:15

Since you are looking for duplicates you could adapt any of the methods shown in this answer.

Using the first one for example:

dupeQ =
Module[{f},
f[y_] := (f[y] := Return[True, Module]; y);
Scan[f, #]; False
] &;


This particular one has an advantage on long lists in that it will "short-circuit" on the first duplicate found rather than proceeding through the end of the list as Union or DeleteDuplicates will. Example:

a = Range[1*^7];
a[[{1, 50}]] = 3.14159;

dupeQ[a] // Timing

{0., True}

a != DeleteDuplicates[a] // Timing

{5.944, True}


For this example I stacked the deck in my favor; by replacing elements in an Integer list with Reals I force the list to unpack. In this situation and with an early duplicate (positions 1 and 50) my method is about 65,000 times faster. For a case with a packed array dupeQ is slower than DeleteDuplicates but not as dramatically:

a = Range[1*^7];
a[[50]] = 7;

dupeQ[a] // Timing

{0.359, True}

a != DeleteDuplicates[a] // Timing

{0.031, True}


Following up on this comment of yours:

Anyway I was wondering if you could save information about the argument repeated: I mean from your approach I can't tell which was the argument repeated.

One could return the duplicate value if one is found and False otherwise:

dupe =
Module[{f},
f[y_] := (f[y] := Return[y, Module]; y);
Scan[f, #]; False
] &;


This function has the same advantage of short-circuiting that the first one does.

• In reference.wolfram.com/mathematica/ref/Return.html there's no mention of a second argument of Return. From the use above, I guess it's something about from which construct you want to return, right? Is that documented somewhere? Jun 13, 2012 at 13:47
• @celtschk yes; I also used it here; the only documentation is Break::nofunc: "The second argument in Break, Continue, or Return is a label that specifies the enclosing function or loop that will be affected. If this label is omitted, the affected function or loop is determined using built-in heuristics." Jun 13, 2012 at 14:13
• Seems that WRI is great at hiding useful information in obscure places :-) Thank you for the information. Jun 13, 2012 at 14:19
• BTW, it just occurred to me that that page speaks about the second parameter of Return, Break and Continue. Actually for Break and Continue there is not even a first parameter documented. A quick test shows that for Break the first parameter gives a return value for the construct, just like Return, while for Continue I couldn't see any effect. Jun 13, 2012 at 14:33
• @celtschk good catch; I need to look into that. Jun 13, 2012 at 14:35

You could use Gather and then check the length of each group :

Gather[{{1, 2, 3}, {2, 0, 0}, {1, 2, 3}, {2, 1, 2}}]

(* {{{1, 2, 3}, {1, 2, 3}}, {{2, 0, 0}}, {{2, 1, 2}}} *)

Length[#] & /@ Gather[{{1, 2, 3}, {2, 0, 0}, {1, 2, 3}, {2, 1, 2}}]

(* {2, 1, 1} *)

• Another great solution...thanks! Jun 13, 2012 at 8:55

A frivolous implementation using patterns:

duplicateQ[list_]:=MemberQ[Tally[list],{_,_?(#>1&)}]


This function uses Tally to arrange the elements of list in bins. For example,

In[2]:= Tally[{1,2,3,1,2}]
Out[2]= {{1,2},{2,2},{3,1}}


Then we look for an element in the output of Tally which looks like {_,n} with $n>1$.

In[3]:= duplicateQ[{{1,2,3},{2,3,4}}]
Out[3]= False

In[4]:= duplicateQ@{{1,2,3},{2,0,0},{1,2,3},{2,1,2}}
Out[4]= True


If we want to keep track of repeated elements, we can use

duplicates[list_] := Cases[Tally[list], {_, _?(# > 1 &)}]

In[6]:= duplicates[{1,4,6,1}]
Out[6]= {{1,2}}

In[7]:= duplicates@{{1,2,3},{2,0,0},{1,2,3},{2,1,2}}
Out[7]= {{{1,2,3},2}}

• Thanks for this solution:it really helps me since is the nearest to my attempts of implementation. Jun 13, 2012 at 8:54

In Version 9, there is a new function DuplicateFreeQ which returns True is there is any duplicate elements in a list. This function is currently not documented, but it is there.

Examples:

snake = {{0, 1}, {0, 0}, {1, 0}, {2, 0}, {3, 0}}
DuplicateFreeQ[snake]
(*True*)

a = {1, 2, 3, 3};
DuplicateFreeQ[a]
(* False *)

a = {1, 2, 3};
DuplicateFreeQ[a]
(* True *)

a = {{1, 1}, {1, 0}, {1, 0}};
DuplicateFreeQ[a]
(*False*)

a = {{1, 1}, {1, 0}, {1, 9}};
DuplicateFreeQ[a]
(*True*)


Update

Table[a = Range@n; a[[n/2]] = 1; Signature[a] // Timing // First, {n, 10^Range@8}]
(* {0., 0., 0., 0., 0., 0., 0.015600, 0.156001} *)

Table[a = Range@n; a[[n/2]] = 1; DuplicateFreeQ[a] // Timing // First, {n, 10^Range@8}]
(* {0., 0., 0., 0., 0., 0., 0.046800, 0.483603} *)


• Nasser, could tell me how this compares to Signature in performance, e.g. Table[ a = Range@n; a[[n/2]] = 1; Signature[a] // Timing // First, {n, 10^Range@8} ]? (This uses about 800 MB memory). Aug 2, 2013 at 18:25
• Yes, thanks. It appears Signature still has value for this application, at least in some cases. Aug 2, 2013 at 20:30
• Now (in version 10) DuplicateFreeQ is documented. Oct 15, 2014 at 19:21

Using UnsameQ:

MultiSetQ[lst_List]:=Not[UnsameQ@@lst]


Usage:

In[2]:= MultiSetQ[{1, 2, 2, 3}]
Out[2]= True
In[3]:= MultiSetQ[{1, 2, 4, 3}]
Out[3]= False

• Nice answer, though not as fast as others. You can make it even more concise: ! UnsameQ @@ lst Jun 29, 2012 at 6:40
• @Mr.Wizard I ran the tests you mention in the comments above and you're right. This is very slow (I had to kill the kernel!). And I thought it would be faster (by the rule of thumb that smaller code in Mathematica -> faster). Why is Union faster? I mean, it returns a sorted version of the list, while UnsameQ will stop comparing (I think) when it finds the first pair of equal elements. How can Union be faster?? Jun 29, 2012 at 21:08
• I don't have an answer to that. It's a good question though, and I'll be thinking about it. Jul 2, 2012 at 16:09
• I think the short answer is this: UnsameQ is designed for handling a low number of arguments. Testing shows that Union and DeleteDuplicates have O(n) time complexity, whereas UnsameQ has O(n^2). UnsameQ is actually faster on tests with a limited number of arguments (it is about even with DeleteDuplicates by 45), so I suppose that it was optimized for that kind of use. Jul 2, 2012 at 16:20