# Find the length of the intersection of two lists including duplicates

I have 2 Lists. The first one includes all the numbers from 1 to 10.

listA={1,2,3,4,5,6,7,8,9,10}


The second includes random numbers, like this:

listB={2,10,2,5,7,15,1000,7,25,600}


I want to find an algorithm that will take any number of the second list listB and compare it to all numbers in listA. If the number in listB is equal to a number in listA, I"ll get 1 as a result. If not it will be 0. As a final result I would like to sum all equal numbers.

Here, for example we have the result 6 because we can find 2 (twice), 7 (twice), 5 and 10 in the two lists. I need a general way because my lists includes data of 10,000 numbers.

• This is ambiguous, e.g., if a number in list 1 is in list 2 twice, does it count twice? And is it a count you're after, or a total of the actual numbers, and if the latter, total of what (matching numbers from both lists, just the matches from one list, ....)? – ciao Apr 27 '16 at 6:33
• Further, do you just want to check for equality in corresponding positions? A full example with unsorted lists and duplicate numbers would really help. – Martin Ender Apr 27 '16 at 6:59
• To count all occurrences you can simply use : Total @ Table[Count[l2, l1[[i]]], {i, 1, Length@l2}] – mgamer Apr 27 '16 at 7:03
• @mgamer: That will overcount if l2 has elements that are repeated in l1... – ciao Apr 27 '16 at 7:14
• @ciao: It´s not a bug, it´s a feature. I did this according to your first comment on this question and counted all occurrences. – mgamer Apr 27 '16 at 9:27

This should be much more efficient for anything beyond small lists:

(Tr[Tally[#1~Join~#2][[;; Length@#1, 2]]] - Length[#1]) &[listA, listB]

• What is it doing, and why is it so much faster? – Jason B. Apr 28 '16 at 12:11
• +1 for superior general solution. I'm very surprised, that Tally is so fast. – LLlAMnYP Apr 28 '16 at 13:56
• @JasonB Tally gives the number of occurrences of the elements of the combined lists A and B but preserves the order in which the elements appear. Therefore the first Length@listA elements of Tally[listA~Join~listB] will give how many times the elements of listB appear in listA plus one. This hinges on the fact that all elements of listA must be distinct, but is otherwise more general than my solution, which demands listA === Range@Length@listA – LLlAMnYP Apr 28 '16 at 14:08

The previous answers seem to have been addressing a rather different (or much more generalized) sort of problem, because as I see this now, we have the following problem statement:

len = 10; (* let's have 10 to be specific, but this is an arbitrary positive integer *)
max = 10^3; (* maximum value of numbers in listB *)
listA = Range[len];
listB = RandomInteger[{1, max}, len];


Then of course a member of listB is a member of listA if it is less than (or equal to) len. So to get the matching numbers we do:

Pick[listB, # <= len &/@ listB]
(* {2, 10, 2, 5, 7, 7} *)


And to get the count of that, simply

Length@%
(* 6 *)


This is slower than @ciao's answer. However, this is almost 2 orders of magnitude faster:

Pick[listB, Sign[listB - len - 1], -1]


And this one is a tiny bit slower, but slightly more general (handles negative integers properly):

Pick[listB, Quotient[listB, len, 1], 0]


Here are the timings for the solutions:

len = 1000000;
max = 10000000;
listA = Range[len];
listB = RandomInteger[{1, max}, len];
(Tr[Tally[#1~Join~#2][[;; Length@#1, 2]]] - Length[#1]) &[listA,
listB] // AbsoluteTiming // First
Pick[listB, # <= len & /@ listB] // AbsoluteTiming // First
Pick[listB, Sign[listB - len - 1], -1] // AbsoluteTiming // First
Pick[listB, Quotient[listB, len, 1], 0] // AbsoluteTiming // First

0.556392 (* ciao *)
0.803501 (* boolean comparison *)
0.0136436 (* Sign *)
0.0171063 (* Quotient *)


Be aware, that while my solution is easily adaptable to the variations of the problem, as stated right now, if listA is also to have random numbers, as originally suggested, ciao's way is probably the fastest (and IMO, really elegant).

• +1 on your interpretation of question and solution - if that is what OP means (a whole list, not a count, and listA always a monotonic range), doing something with Pick et al. will be quite quick. – ciao Apr 28 '16 at 22:10
• @ciao "A whole list, not a count" - sure I omitted the // Length in the timings, but that's a trivial part, right? Wondering, if something smart could be done with Ordering and friends. – LLlAMnYP Apr 29 '16 at 8:25
• @Not sure the Ordering tricks would be so fast here - I considered but rejected offhand. I think, though, that Tr@Unitize@Clip[listB, {1, len}, {0, 0}] could be quick - but away from machine so can't test right now. – ciao Apr 29 '16 at 8:38
• @ciao Yes, quite. 8-9ms averaged over 100 runs on the same machine. I was thinking of this approach, but overlooked the extra arguments of Clip that would make it work. – LLlAMnYP Apr 29 '16 at 8:50

I am not sure what the exact aim is. In the following it is assumed:

• 2 random samples from a range of integers (distinct elements) of equal length
• the aim is to determine size of intersection:

f[n_, s_] := Module[{a = RandomSample[Range[n], s], b = RandomSample[Range[n], s], j, u, c, r}, c = Intersection[a, b]; r = # -> Style[#, Bold, Red] & /@ c; {a /. r, b /. r, Length@c}]

Much of above is just window dressing.

Examples:

Grid[Table[f[10, 5], {5}]] or

Grid[Table[f[20, 10], {5}]] Now that the question has been restated, you can use a shortened version of the answer suggested by mgamer,

B = {2, 10, 2, 5, 7, 15, 1000, 7, 25, 600};
A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
Count[B, #] & /@ A // Total
(* 6 *)


Or you could use MemberQ and Boole,

Boole@MemberQ[A, #] & /@ B // Total
(* 6 *)


Or Select, MemberQ, and Length

Select[B, MemberQ[A, #] &] // Length
(* 6 *)


If speed is an issue, and the B list is very large, then the Boole method is slightly faster, and the Select method is by far the slowest.

SeedRandom;
A = Range;
B = RandomInteger[10000, 10^6];
Count[B, #] & /@ A // Total // AbsoluteTiming
Boole@MemberQ[A, #] & /@ B // Total // AbsoluteTiming
Select[B, MemberQ[A, #] &] // Length // AbsoluteTiming
(* {0.113349, 10012} *)
(* {0.135395, 10012} *)
(* {4.06878, 10012} *)


If the A list gets larger, then the difference between the Count and Boole methods is minimal, but Select is much worse,

SeedRandom;
A = Range;
B = RandomInteger[10000, 10^6];
Count[B, #] & /@ A // Total // AbsoluteTiming
Boole@MemberQ[A, #] & /@ B // Total // AbsoluteTiming
Select[B, MemberQ[A, #] &] // Length // AbsoluteTiming
(* {0.896079, 100334} *)
(* {0.865092, 100334} *)
(* {25.8521, 100334} *)

• Good answer. What is this @* syntax called? Seems to be handy... is it new in 10? – Theo Tiger Apr 27 '16 at 11:54
• @TheoTiger, it is short for Composition, so in this case it saves me from having to type Boole[SameQ[#]]& - I believe the shorthand is new in 10.0 – Jason B. Apr 27 '16 at 12:21
• Thanks! Just looked it up, the infix is indeed new in 10. I always did something like Boole@SameQ@##&, but this is much nicer. – Theo Tiger Apr 27 '16 at 13:58
• Thank you very much. I guess there is also a possibility to get a Table output of all equal numbers in both tables. How can I do it? – Danny Apr 28 '16 at 7:43
• Select[B, MemberQ[A, #] &] returns {2, 10, 2, 5, 7, 7} – Jason B. Apr 28 '16 at 7:44