Multisets

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.