22
$\begingroup$

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.

Improve this question
$\endgroup$

9 Answers 9

Reset to default
17
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Gianpiero Cea
    Commented Jun 13, 2012 at 8:41
  • 1
    $\begingroup$ Any reason why you prefer Union over DeleteDuplicates? $\endgroup$
    – Ajasja
    Commented Jun 13, 2012 at 12:10
  • $\begingroup$ @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. $\endgroup$
    – jVincent
    Commented Jun 13, 2012 at 12:49
  • 2
    $\begingroup$ You might want to restore this to Union. Compare these timings: a = RandomInteger[10, {100000, 50}]; then Timing[Union@a;] and Timing[DeleteDuplicates@a;] $\endgroup$
    – Mr.Wizard
    Commented Jun 13, 2012 at 14:29
  • $\begingroup$ @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. $\endgroup$
    – jVincent
    Commented Jun 13, 2012 at 17:44
29
$\begingroup$

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.

Improve this answer
$\endgroup$
11
  • 3
    $\begingroup$ +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. $\endgroup$
    – Sjoerd C. de Vries
    Commented Jun 13, 2012 at 12:51
  • 1
    $\begingroup$ 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... $\endgroup$
    – Sjoerd C. de Vries
    Commented Jun 13, 2012 at 13:04
  • $\begingroup$ So, perhaps canonical after all. $\endgroup$
    – Sjoerd C. de Vries
    Commented Jun 13, 2012 at 13:15
  • 4
    $\begingroup$ @Sjoerd I honestly wish that were an option; as I think you know I would like to see a collaborative-answer feature added. $\endgroup$
    – Mr.Wizard
    Commented Jun 13, 2012 at 13:28
  • 1
    $\begingroup$ @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 $\endgroup$
    – jVincent
    Commented Jun 13, 2012 at 18:16
13
$\begingroup$ 
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}}  *)
Improve this answer
$\endgroup$
10
$\begingroup$

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

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

Or:

DuplicatesQ[{___,x_,___,x_,___}] := True
DuplicatesQ[_] := False
Improve this answer
$\endgroup$
1
  • $\begingroup$ +1 for elegance, but be warned this is quite slow. $\endgroup$
    – Mr.Wizard
    Commented Jun 13, 2012 at 11:15
9
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ 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? $\endgroup$
    – celtschk
    Commented Jun 13, 2012 at 13:47
  • 1
    $\begingroup$ @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." $\endgroup$
    – Mr.Wizard
    Commented Jun 13, 2012 at 14:13
  • 1
    $\begingroup$ Seems that WRI is great at hiding useful information in obscure places :-) Thank you for the information. $\endgroup$
    – celtschk
    Commented Jun 13, 2012 at 14:19
  • 4
    $\begingroup$ 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. $\endgroup$
    – celtschk
    Commented Jun 13, 2012 at 14:33
  • $\begingroup$ @celtschk good catch; I need to look into that. $\endgroup$
    – Mr.Wizard
    Commented Jun 13, 2012 at 14:35
7
$\begingroup$

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} *)
Improve this answer
$\endgroup$
1
  • $\begingroup$ Another great solution...thanks! $\endgroup$
    – Gianpiero Cea
    Commented Jun 13, 2012 at 8:55
7
$\begingroup$

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}}
Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for this solution:it really helps me since is the nearest to my attempts of implementation. $\endgroup$
    – Gianpiero Cea
    Commented Jun 13, 2012 at 8:54
5
$\begingroup$

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.

Mathematica graphics

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

Answering comment below.

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} *)

Mathematica graphics

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$
    – Mr.Wizard
    Commented Aug 2, 2013 at 18:25
  • $\begingroup$ Yes, thanks. It appears Signature still has value for this application, at least in some cases. $\endgroup$
    – Mr.Wizard
    Commented Aug 2, 2013 at 20:30
  • 1
    $\begingroup$ Now (in version 10) DuplicateFreeQ is documented. $\endgroup$
    – ybeltukov
    Commented Oct 15, 2014 at 19:21
4
$\begingroup$

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
Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Nice answer, though not as fast as others. You can make it even more concise: ! UnsameQ @@ lst $\endgroup$
    – Mr.Wizard
    Commented Jun 29, 2012 at 6:40
  • 2
    $\begingroup$ @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?? $\endgroup$
    – a06e
    Commented Jun 29, 2012 at 21:08
  • $\begingroup$ I don't have an answer to that. It's a good question though, and I'll be thinking about it. $\endgroup$
    – Mr.Wizard
    Commented Jul 2, 2012 at 16:09
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mr.Wizard
    Commented Jul 2, 2012 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.