# Multisets

## Contents

## Definition

In mathematics, an unordered collection of distinct objects is called a set. If duplicates are allowed, the collection is called a multiset. The concept of multisets dates from the late 1880s; the term dates from the 1970s.

## Example

A common example of a multiset is the decomposition of an integer into its prime factors, each of which may occur multiple times. For example, 600 may be factored into the multiset 2 2 2 3 5 5, and 2100 into 2 2 3 5 5 7.

Two useful properties of a multiset (from which the original multiset may be reconstructed) is the **Underlying Set of Unique Elements** along their **Multiplicities**. For the two multisets above the two properties are

3 1 2 2 3 5 |
and | 2 1 2 1 2 3 5 7 |

Two common operations performed between multisets are **Union** and **Intersection**.

**Multiset Union** on L and R is defined as the multiset whose underlying set is the set union of the underlying sets of L and R, and whose multiplicities are the larger of the multiplicities of the corresponding elements of L and R.

For L←2 2 2 3 5 5 and R←2 2 3 5 5 7 the multiset union is 2 2 2 3 5 5 7. Note that, for example, there are three 2s in the result because that is the larger of the number of 2s in L (3) and R (2).

**Multiset Intersection** on L and R is defined the same as for **Multiset Union** except that the smaller of the multiplicities is taken instead of the larger. For the two multisets above, the multiset intersection is 2 2 3 5 5 where there are two 2s in the result because that's the smaller of the number of 2s in L (3) and R (2), and there are no 7s in the result because that's the smaller of the number of 7s in L (0) and R (1).

Interestingly, in the context of prime factorization, Multiset Union is the direct analogue of **Least Common Multiple** and Multiset Intersection is **Greatest Common Divisor**. Using the notation of ∪⍦ for Multiset Union and ∩⍦ for Multiset Intersection, then for the two multisets above,

L∪⍦R ←→ 2 2 2 3 5 5 7 and

L∩⍦R ←→ 2 2 3 5 5

The Least Common Multiple of two original numbers ×/L ←→ 600 and ×/R ←→ 2100 is

(×/L)∧×/R

4200

×/L∪⍦R

4200

and the Greatest Common Divisor is

(×/L)∨×/R

300

×/L∩⍦R

300

## Notation

We slipped in a symbol in the example above that needs to be explained. There are a dozen or so APL primitive functions we'd like to define on multisets. One way is to come up with a dozen new symbols to represent those multiset functions; another is to define a **Multiset Operator** that can be applied to the APL primitives which is the approach taken here, and that symbol is (⍦). This operator is different from previous operators in APL in that it applies to a select set of primitive functions and no others -- no system functions, not user-defined functions, and no derived functions. In that sense it's more like a digraph such as . and : in J.

Multisets in an APL context are vectors of arbitrary items with various operations defined on them (monadically), but mostly between them (dyadically). Instead of

## Acknowledgments

The idea of defining Multisets in an APL context is due to Patrick Parks of APL2000, Inc.