A partition of a set
\(S=\left\lbrace 1,\ldots,n\right\rbrace\) is a family of
sets \(T_1,\ldots,T_k\) satisfying
\(i\neq j\longrightarrow T_i\cap
T_j=\emptyset\)
\(\cup_{i=1}^kT_k=S\)
\(T_i\neq\emptyset\) for \(i=1,\ldots,
k\)
The induced equivalence relation has \(i\sim j\) if and
only if \(i\) and \(j\) belong to the same partition. Equivalence
classes of \(S=\left\lbrace 1,\ldots,n\right\rbrace\)
may be listed using listParts(). There are exactly fifteen ways
to partition a set of four elements:
| \((1234)\) |
| \((123)(4), (124)(3), (134)(2), (234)(1)\) |
| \((12)(34), (13)(24), (14)(23)\) |
| \((12)(3)(4), (13)(2)(4), (23)(1)(4), (24)(1)(3),
(34)(1)(2)\) |
| \((1)(2)(3)(4)\) |
Note that \((12)(3)(4)\) is the same partition as, for example,
\((3)(4)(21)\) as the equivalence relation is the same.
Consider partitions of a set \(S\) of five elements (named
\(1,2,3,4,5\)) with sizes 2,2,1. These may be enumerated as
follows:
> u <- c(2,2,1)
> setparts(u)
[1,] 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3
[2,] 2 2 3 1 1 1 2 2 3 2 2 3 1 1 1
[3,] 3 2 2 3 2 2 1 1 1 3 2 2 2 1 2
[4,] 2 3 2 2 3 2 3 2 2 1 1 1 2 2 1
[5,] 1 1 1 2 2 3 2 3 2 2 3 2 1 2 2
See how each column has two 1s, two 2s and one 3. This is because the
first and second classes have size two, and the third has size one.
The first partition, x=c(1,2,3,2,1), is read “class 1
contains elements 1 and 5 (because the first and fifth element of
x is 1); class 2 contains elements 2 and 4 (because the second
and fourth element of x is 2); and class 3 contains element 3
(because the third element of x is 3)”. Formally, class
i has elements which(x==u[i]).
You can change the print method by setting, eg,
options(separator="").
Functions vec_to_set() and vec_to_eq() are low-level
helper functions. These take an integer vector, typically a column of a
matrix produced by setparts() and return their set
representation.
Function restrictedsetparts() provides a matrix-based alternative
to listParts(). Note that the vector must be in
non-increasing order:
restrictedsetparts(c(a=2,b=2,c=1))
a 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2
a 5 5 5 2 2 2 3 3 3 4 4 4 5 3 4
b 2 2 3 4 3 3 2 2 4 2 2 3 3 4 3
b 4 3 4 5 5 4 5 4 5 5 3 5 4 5 5
c 3 4 2 3 4 5 4 5 2 3 5 2 1 1 1
Above, we set partitions of \(\left\lbrace
1,2,3,4,5\right\rbrace\) into equivalence classes of sizes 2,2,1.
The first column, for example, corresponds to
\(\left\lbrace1,5\right\rbrace\left\lbrace2,4\right\rbrace\left\lbrace3\right\rbrace\).
Note the absence of
\(\left\lbrace5,1\right\rbrace\left\lbrace2,4\right\rbrace\left\lbrace3\right\rbrace\).
and
\(\left\lbrace2,4\right\rbrace\left\lbrace1,5\right\rbrace\left\lbrace3\right\rbrace\)
which would correspond to the same (set) partition; compare
multinomial(). Observe that the individual subsets are not
necessarily sorted.
Function restrictedsetparts2() uses an alternative implementation
which might be faster under some circumstances.