Wolfram Research

MultisetIntersection

Contributed by: Robert B. Nachbar (Wolfram Solutions)

Source Notebook

Perform the intersection operation on multisets

ResourceFunction["MultisetIntersection"][list1,list2,]

gives a sorted list of the elements common to all the listi. The number of occurances of each distinct element is the minimum of the counts in each of the listi.

ResourceFunction["MultisetIntersection"][assoc1,assoc2,]

gives an Association where the keys are the union of the keys in the associations associ and the values are the minimum of the merged values.

Details and Options

If the listi are considered as multisets, ResourceFunction["MultisetIntersection"] gives their intersection.
The listi must have the same head, but it need not be List.
The values of associ must be counts, that is, non-negative Integer values.

Examples

Basic Examples

Find largest subsets of elements common to all the lists given:

In[1]:=
ResourceFunction[
 "MultisetIntersection"][{1, 1, 2, 3}, {3, 1, 1, 1, 4}, {4, 1, 1, 3, 3}]
Out[1]=

Multisets as Association of counts :

In[2]:=
ResourceFunction[
 "MultisetIntersection"][<|"a" -> 3, "b" -> 1, "c" -> 2, "d" -> 1|>,
 <|"a" -> 2, "b" -> 2, "c" -> 2, "e" -> 1|>,
 <|"a" -> 1, "b" -> 2, "c" -> 2, "e" -> 2|>]
Out[2]=

Scope

MultisetIntersection works with any head, not just List:

In[3]:=
ResourceFunction["MultisetIntersection"][f[a, b], f[c, a], f[b, b, a]]
Out[3]=

Properties and Relations

If there is no intersection, the result is {}:

In[4]:=
ResourceFunction["MultisetIntersection"][{a, b, b, c}, {d, e, f, f}]
Out[4]=

If there is no intersection of the Association multisets, the result is <||>:

In[5]:=
ResourceFunction[
 "MultisetIntersection"][<|a -> 1, b -> 2, c -> 1|>, <|d -> 1, e -> 1,
   f -> 2|>]
Out[5]=

Compare to Intersection:

In[6]:=
ResourceFunction[
 "MultisetIntersection"][{a, b, a, d, d}, {d, a, d, e, d}, {c, d, a, d}]
Out[6]=
In[7]:=
Intersection[{a, b, a, d, d}, {d, a, d, e, d}, {c, d, a, d}]
Out[7]=

Resource History

See Also