Claddis (version 0.7.0)

permute_restricted_compositions: Permute all ways to place n items into m bins

Description

Given a positive integer, n, and a number of bins (m), permutes all possible compositions.

Usage

permute_restricted_compositions(n, m_labels, allow_zero = FALSE)

Value

A matrix where each row is a unique restricted composition of n and each column is a labelled bin.

Arguments

n

A positive integer.

m_labels

A character vector of labels for m.

allow_zero

A logical indicating whether or not each bin should (TRUE) or should not (FALSE) be allowed to be zero.

Author

Graeme T. Lloyd

Details

Every way that an integer (n) can be divided up into m bins can be permuted using a restricted version of the mathematical concept of compositions. In practice this function is designed to distribute the states for n tips across m states (e.g., with permute_tipstates), but many other uses are conceivable and hence this is included here as a general function.

This algorithm reuses code from the multicool (Curran et al. 2021) and partitions (Hankin 2006) packages.

The number of restricted compositions is given by the k-dimensional extension of triangular numbers (Baumann 2019):

• If allow_zero = TRUE, the binomial coefficient, n choose k, where n = n + m - 1 and k = m.

• If allow_zero = FALSE, the binomial coefficient, n choose k, where n = n - 1 and k = m.

References

Baumann, M. H., 2019. Die k-dimensionale Champagnerpyramide. Mathematische Semesterberichte, 66, 89-100.

Curran, J., Williams, A., Kelleher, J. and Barber, D., 2021. multicool: Permutations of Multisets in Cool-Lex Order. R package version 0.1-12. https://CRAN.R-project.org/package=multicool.

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

Examples

# Permute all the ways eight can be assigned to four bins (A, C, G, T),
# with each bin assigned at least one:
permute_restricted_compositions(
  n = 8,
  m_labels = c("A", "C", "G", "T"),
  allow_zero = FALSE
)