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

In graemetlloyd/Claddis: Measuring Morphological Diversity and Evolutionary Tempo

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)

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.

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.

Value

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

Author(s)

Graeme T. Lloyd [e-mail]

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
)

graemetlloyd/Claddis documentation built on May 9, 2024, 8:07 a.m.