# 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. – Gianpiero Cea Jun 13 '12 at 8:41
Any reason why you prefer Union over DeleteDuplicates? – Ajasja Jun 13 '12 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. – jVincent Jun 13 '12 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;] – Mr.Wizard Jun 13 '12 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. – jVincent Jun 13 '12 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. – Sjoerd C. de Vries Jun 13 '12 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... – Sjoerd C. de Vries Jun 13 '12 at 13:04
So, perhaps canonical after all. – Sjoerd C. de Vries Jun 13 '12 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. – Mr.Wizard Jun 13 '12 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 – jVincent Jun 13 '12 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. – Mr.Wizard Jun 13 '12 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? – celtschk Jun 13 '12 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." – Mr.Wizard Jun 13 '12 at 14:13
Seems that WRI is great at hiding useful information in obscure places :-) Thank you for the information. – celtschk Jun 13 '12 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. – celtschk Jun 13 '12 at 14:33
@celtschk good catch; I need to look into that. – Mr.Wizard Jun 13 '12 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! – Gianpiero Cea Jun 13 '12 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. – Gianpiero Cea Jun 13 '12 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). – Mr.Wizard Aug 2 '13 at 18:25
Yes, thanks. It appears Signature still has value for this application, at least in some cases. – Mr.Wizard Aug 2 '13 at 20:30
Now (in version 10) DuplicateFreeQ is documented. – ybeltukov Oct 15 '14 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 – Mr.Wizard Jun 29 '12 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?? – becko Jun 29 '12 at 21:08
I don't have an answer to that. It's a good question though, and I'll be thinking about it. – Mr.Wizard Jul 2 '12 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. – Mr.Wizard Jul 2 '12 at 16:20