setparts {partitions}

Set partitions

Description

Enumeration of set partitions

Usage

setparts(x)
listParts(x,do.set=FALSE)
vec_to_set(vec)
vec_to_eq(vec)

Arguments

x

If a vector of length 1, the size of the set to be partitioned. If a vector of length greater than 1, return all equivalence relations with equivalence classes with sizes of the elements of x. If a matrix, return all equivalence classes with sizes of the columns of x

do.set

Boolean, with TRUE meaning to return the set partitions in terms of sets (as per sets package) and default FALSE meaning to present the result in terms of equivalence classes

vec

An integer vector representing a set partition

Details

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(). Thus

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, option(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.

Value

Returns a matrix each of whose columns show a set partition; an object of class "partition". Type ?print.partition to see how to change the options for printing.

Note

The clue package by Kurt Hornik contains functionality for partitions (specifically cl_meet() and cl_join()) which might be useful. Option do.set invokes functionality from the sets package by Meyer et al.

Note carefully that setparts(c(2,1,1)) does not enumerate the ways of placing four numbered balls in three boxes of capacities 2,1,1. This is because there are two boxes of capacity 1, and swapping the balls between these boxes gives the same set partition (because sets are unordered). To do this, use multinomial(c(a=2,b=1,c=1)). See the setparts vignette for more details.

Author(s)

Luke G. West (C++) and Robin K. S. Hankin (R); listParts() provided by Diana Tichy

References

• R. K. S. Hankin 2006. Additive integer partitions in R. Journal of Statistical Software, Code Snippets 16(1)

• R. K. S. Hankin 2007. “Set partitions in R”. Journal of Statistical Software, Volume 23, code snippet 2

• Kurt Hornik (2017). clue: Cluster ensembles. R package version 0.3-53. https://CRAN.R-project.org/package=clue

• Kurt Hornik (2005). A CLUE for Cluster Ensembles. Journal of Statistical Software 14/12. doi:10.18637/jss.v014.i12

See Also

parts, print.partition

Examples

setparts(4)                # all partitions of a set of 4 elements

setparts(c(3,3,2))         # all partitions of a set of 8 elements
                           # into sets of sizes 3,3,2.


listParts(c(2,2,1))        # all 15 ways of defining subsets of
                           # {1,2,3,4,5} with sizes 2,2,1

jj <- restrictedparts(5,3)
setparts(jj)               # partitions of a set of 5 elements into
                           # at most 3 sets

listParts(jj)              # The induced equivalence classes




jj <- restrictedparts(6,3,TRUE)
setparts(jj)               # partitions of a set of 6 elements into
ncol(setparts(jj))         # _exactly_ 3 sets; cf StirlingS2[6,3]==90


setparts(conjugate(jj))    # partitions of a set of 5 elements into
                           # sets not exceeding 3 elements


setparts(diffparts(5))     # partitions of a set of 5 elements into
                           # sets of different sizes