In RobinHankin/partitions: Additive Partitions of Integers

knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>",
  fig.path = "man/figures/README-",
  out.width = "100%"
)

Overview

The partitions package provides efficient vectorized code to enumerate solutions to various integer equations. For example, we might note that

$$ 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1 $$

and we might want to list all seven in a consistent format (note here that each sum is written in nonincreasing order, so $3+1$ is considered to be the same as $1+3$).

Installation

You can install the released version of wedge from CRAN with:

# install.packages("partitions")  # uncomment this to install the package
library("partitions")

The partitions package in use

To enumerate the partitions of 5:

parts(5)

(each column is padded with zeros). Of course, larger integers have many more partitions and in this case we can use summary():

summary(parts(16))

Sometimes we want to find the unequal partitions (that is, partitions without repeats):

summary(diffparts(16))

Restricted partitions

Sometimes we have restrictions on the partition. For example, to enumerate the partitions of 9 into 5 parts we would use restrictedparts():

summary(restrictedparts(9,5))

and if we want the partitions of 9 into parts not exceeding 5 we would use the conjugate of this:

summary(conjugate(restrictedparts(9,5)))

Block parts

Sometimes we have restrictions on each element of a partition and in this case we would use blockparts():

summary(blockparts(1:6,10))

which would show all solutions to $\sum_{i=1}^6a_i=9$, $a_i\leq i$.

Compositions

Above we considered $3+2$ and $2+3$ to be the same partition, but if these are considered to be distinct, we need the compositions, not partitions:

compositions(4)

Set partitions

A set of 4 elements, WLOG ${1,2,3,4}$, may be partitioned into subsets in a number of ways and these are enumerated with the setparts() function:

setparts(4)

In the above, column 2 3 1 1 would correspond to the set partition ${{3,4},{1},{2}}$.

Multiset

Knuth deals with multisets (that is, a generalization of the concept of set, in which elements may appear more than once) and gives an algorithm for enumerating a multiset. His simplest example is the permutations of ${1,2,2,3}$:

multiset(c(1,2,2,3))

It is possible to answer questions such as the permutations of the word "pepper":

library("magrittr")

"pepper"    %>%
strsplit("") %>%
unlist        %>%
match(letters) %>%
multiset        %>%
apply(2,function(x){x %>% `[`(letters,.) %>% paste(collapse="")})

Riffle shuffles

A $(p,q)$ riffle shuffle is an ordering $\sigma$ of integers $1,2,\ldots,p+q$ such that $1,\ldots p$ and $p+1,\ldots p+q$ appear in their original order: if $1\leq i_1 < i_2\leq p$, then $\sigma(i_1) < \sigma(i_2)$, and if $p+1\leq j_1 < j_2\leq p+q$, then $\sigma(j_1) < \sigma(i_j)$. The two groups of integers appear in their original order. To enumerate all $(p,q)$ riffles, use riffle():

riffle(2,4)

To enumerate all riffles with sizes $v_1,v_2,\ldots,v_r$, use genrif():

genrif(1:3)

Further information

For more detail, see the package vignettes

vignette("partitionspaper")
vignette("setpartitions")
vignette("scrabble")

RobinHankin/partitions documentation built on Feb. 28, 2024, 12:08 a.m.