Multisets: a set that counts¶

Level: 101 · for anyone who asked "what the heck is a multiset" after a set threw away their duplicates

One line: A multiset is a function from a set to the natural numbers, a count for each member, which is what a histogram, a prime factorisation and Python's Counter all are; its intersection is the minimum of counts and its union the maximum, which makes gcd and lcm the ∩ and ∪ of factorisations, and the one set law it loses is idempotence of the sum, because [2] + [2] is [2, 2].

The definition¶

A set is its members, so {1, 1, 1} is {1}: repetition is not membership, as what is a set? insists. When the repetition is the information, the right object is a multiset: a function M from a set S to ℕ, giving each x its multiplicity M(x). The members are the x with M(x) > 0, the size is the sum of the counts, and the usual spelling lists members with repetition, [2, 2, 2, 5, 7, 7]. Simovici and Djeraba define it this way in their section 1.5; Python's collections.Counter is the same object with dictionary syntax, and section 1 of the program shows BANANA both ways.

The operations, and which laws survive¶

Counts replace membership, so each operation becomes arithmetic on counts, section 2: intersection takes the minimum of the two counts, union the maximum, sum adds them, difference subtracts and drops what goes to zero, and M ⊆ N means every count in M is at most the count in N. Union and intersection keep every law of the algebra of sets that does not mention a complement: commutative, associative, idempotent, each distributing over the other. The sum is new and is not idempotent, [2] + [2] = [2, 2], which is why multisets behave like numbers under + and like sets under ∪, section 4. There is no complement, since a count has no ceiling to be subtracted from, which is the multiset form of the fact that a complement needs a universe.

Where it is used¶

Number theory, section 3: the prime factorisation of n is a multiset of primes, and for every pair of numbers up to 60 the program checks that gcd is the intersection of the factorisations, lcm the union, and the product the sum. "m divides n" is "the factorisation of m is a sub-multiset of that of n", the multiset version of the factor-set fact on the set katas. Counting, section 5: the multisets of size k drawn from n kinds number C(n + k − 1, k), by stars and bars, against C(n, k) for sets. Data: a histogram, a bag of words, a shopping basket, and Ashlock's "weights of all people in Canada" from the set katas, section 6, are multisets, and the set behind each is what remains when the counts are forgotten.

What the program prints¶

Verified output of multisets.py — regenerated by tools/run_examples.py, never hand-typed.

1. BANANA AS A SET AND AS A MULTISET
   set("BANANA")     = ['A', 'B', 'N']: 3 members, repetition forgotten
   Counter("BANANA") = {'A': 3, 'B': 1, 'N': 2}: each letter with its multiplicity
   A multiset M on a set S is a function M: S -> N giving each member a count;
   its members are the x with M(x) > 0, and |M| is the sum of the counts.
   |Counter("BANANA")| = 6 = len("BANANA")

2. THE OPERATIONS: & IS MIN, | IS MAX, + ADDS, - SUBTRACTS AND DROPS ZEROS
   a = [a, a, b, b, b, c]   b = [a, b, b, d, d]
   a & b (min)          = [a, b, b]
   a | b (max)          = [a, a, b, b, b, c, d, d]
   a + b (sum)          = [a, a, a, b, b, b, b, b, c, d, d]
   a - b (difference)   = [a, b, c]
   a ⊆ b for multisets means every count in a is at most the count in b:
   a ⊆ a | b: True   a & b ⊆ a: True   a ⊆ b: False

3. GCD AND LCM ARE ∩ AND ∪ OF PRIME FACTORISATIONS, THE PRODUCT IS +
   360 = [2, 2, 2, 3, 3, 5]
   84 = [2, 2, 3, 7]
   360 & 84 = [2, 2, 3] = 12 = gcd;   360 | 84 = [2, 2, 2, 3, 3, 5, 7] = 2520 = lcm
   checked for all x, y in 1..60: True.  'm divides n' is 'factors(m) ⊆ factors(n)', as a multiset.

4. WHICH SET LAWS SURVIVE
   c = [a, a, b]:  c | c = [a, a, b] (idempotent, like ∪)   c + c = [a, a, a, a, b, b] (not: like + on numbers)
   c & c = [a, a, b] (idempotent)   c - c = [] (empty)
   |, & and + are commutative and associative; | and & distribute over each other;
   there is no complement, since a count has no 'everything above it' to subtract from.

5. COUNTING MULTISETS: k THINGS FROM n KINDS, REPETITION ALLOWED
   multisets of size 2 from {a, b, c}: 6: aa, ab, ac, bb, bc, cc
   formula C(n + k − 1, k) = C(4, 2) = 6; against C(n, k) = 3 sets of size 2.
   Stars and bars: write k stars and n − 1 bars, aa|b| is a a b; choose where the bars go.

6. WHERE THE SET WAS THE WRONG TYPE
   'the weights of all people in Canada', Ashlock's problem 2.1: list [70, 82, 70, 65, 82, 82]
   as a set [65, 70, 82] loses the count; as a multiset {65: 1, 70: 2, 82: 3} keeps it,
   and 'all weights at least one person had' is exactly the set. A histogram is a
   multiset; so is a prime factorisation, a shopping basket, a bag of words.

Po polsku, w skrócie¶

Multizbiór (wielozbiór) to zbiór, który liczy: funkcja M ze zbioru S w liczby naturalne, podająca krotność każdego elementu; zapisuje się go jak zbiór z powtórzeniami, [2, 2, 2, 5, 7, 7], a w Pythonie jest nim collections.Counter. Przekrój to minimum krotności, suma mnogościowa to maksimum, a dodawanie dodaje krotności; dodawanie nie jest idempotentne ([2] + [2] = [2, 2]), dopełnienia nie ma. Rozkład liczby na czynniki pierwsze jest multizbiorem, i program sprawdza dla wszystkich par do 60, że NWD to przekrój rozkładów, NWW to ich suma mnogościowa, a iloczyn to dodawanie. Multizbiorów rozmiaru k z n rodzajów jest C(n + k − 1, k). Histogram, worek słów i lista wag mieszkańców Kanady z zadania Ashlocka to multizbiory; zbiór to to, co zostaje po zapomnieniu krotności.

Auf Deutsch: Stichwörter¶

Eine Multimenge zählt, wie oft ein Element vorkommt; Vereinigung, Schnitt und Summe bekommen dadurch verschiedene Bedeutungen.

Stichwörter: Multimenge (multiset), Vielfachheit, Summe, Vereinigung als Maximum, Schnitt als Minimum, Primfaktorzerlegung, Counter in Python.

Run it yourself¶

From the root of your clone of this repository:

python3 04_Sets/multisets/examples/multisets.py