1
$\begingroup$

I do apologize if this is a duplication. I did find a question that appears close to describing something of what I'm looking for, but I'm just not "seeing" the complete picture (maybe):

https://math.stackexchange.com/questions/591071/counting-matches-in-a-set - answered in comments without details for someone at my skill level; however, I am sure a simple mathematical expression (and possible term) exists for this concept, but mathematics is not my main area.

I have set A = {"Hey", "how", "are", "you"} and set B = {"Hey", "you"}, when compared, the result would be 2, because two elements in B are also in A. Further, if B = {"Hey", "are", "you", "John"}, when compared, the result would be 3, because while |A| and |B| is four, only three elements exist in common in both A and B.

How do I notate this concept? How do I describe this concept in plain language? And, if possible, what is the algorithmic representation of this concept?

Cheers.

$\endgroup$
4
  • 2
    $\begingroup$ What you are interested in is the cardinality of the intersection of the two sets, i.e. $|A \cap B|$. Are you asking for an algorithm to compute this, or just the mathematical notation for it? $\endgroup$
    – JimmyK4542
    Commented Aug 3, 2014 at 4:17
  • $\begingroup$ @JimmyK4542 - Good question. For the purposes of completeness and posterity to the community an algorithm would be nice. For my personal purposes, I think "cardinality of the intersection of the two sets, i.e. |A∩B|", actually does the trick. $\endgroup$
    – Josh Bruce
    Commented Aug 3, 2014 at 4:22
  • 1
    $\begingroup$ There's really no algorithm, since sets can include pretty much anything. I'm not quite sure what your question is, though. $\endgroup$
    – Asaf Karagila
    Commented Aug 3, 2014 at 4:37
  • $\begingroup$ @AsafKaragila - I believe JimmyK4542 answered my questions (see updates), just not as an answer I can accept via stack. $\endgroup$
    – Josh Bruce
    Commented Aug 3, 2014 at 4:43

1 Answer 1

2
$\begingroup$

Probably the easiest algorithm begins by sorting $A$ and $B$ into order. Then as long as neither $A$ nor $B$ is empty, repeat the following:

  • If the first item of $A$ is equal to the first item of $B$, discard both, and increment a counter.
  • Otherwise, discard the first item of $A$ or the first item of $B$, whichever comes first in sorted order.

When either $A$ or $B$ becomes empty, stop; the counter contains the number of common elements.

For large sets, it is more efficient to use a hash table.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .