parts | R Documentation |
Given an integer, return a matrix whose columns enumerate various partitions.
Function parts()
returns the unrestricted partitions; function
diffparts()
returns the unequal partitions; function
restrictedparts()
returns the restricted partitions; function
blockparts()
returns the partitions subject to specified
maxima; and function compositions()
returns all compositions
of the argument.
parts(n)
diffparts(n)
restrictedparts(n, m, include.zero=TRUE, decreasing=TRUE)
blockparts(f, n=NULL, include.fewer=FALSE)
compositions(n, m=NULL, include.zero=TRUE)
multiset(v,n=length(v))
mset(v)
multinomial(v)
allbinom(n,k)
n |
Integer to be partitioned. In function |
m |
In functions |
include.zero |
In functions |
include.fewer |
In function |
decreasing |
In |
f |
In function |
v |
An integer vector. In function |
k |
In function |
Function parts()
uses the algorithm in Andrews.
Function diffparts()
uses a very similar algorithm that I
have not seen elsewhere. These functions behave strangely if given
an argument of zero.
Function restrictedparts()
uses the algorithm in
Andrews, originally due to Hindenburg. For partitions into at most
m
parts, the same Hindenburg's algorithm is used but with a
start vector of c(rep(0,m-1),n)
.
Functions parts()
and restrictedparts()
overlap in
functionality. Note, however, that they can return identical
partitions but in a different order: parts(6)
and
restrictedparts(6,6)
for example.
If \mjseqnm>n, the partitions are padded with zeros.
Function blockparts()
enumerates the compositions of an
integer subject to a maximum criterion: given vector
\mjeqny=(y_1,...,y_n)y=(y_1,...,y_p) all sets of
\mjeqna=(a_1,...,a_n)a=(a_1,...,a_p) satisfying
\mjeqn\sum_i=1^pa_i=nsum(a_i)=n subject to \mjeqn0\leq a_i\leq
y_i0 <= a_i <= y_i for all i
are given in lexicographical
order. If argument y
includes zero elements, these are
treated consistently (ie a position with zero capacity).
If n
takes its default value of NULL
, then the
restriction \mjeqn\sum_i=1^pa_i=nsum(a_i)=n is relaxed (so that
the numbers may sum to anything). Note that these solutions are not
necessarily in standard form, so functions durfee()
and
conjugate()
may fail.
With a single argument, compositions(n)
returns all
\mjeqn2^n-12^(n-1) ways of partitioning an integer; thus
4+1+1
is distinct from 1+4+1
or 1+1+4
. With
two arguments, compositions(n,m)
returns all nonnegative
solutions to \mjeqnx_1+\cdots+x_m=nx_1+...+x_m=n. This function
is different from all the others in the package in that it is
written in R; it is not clear that C would be any
faster.
Function multiset(v)
returns all ways of ordering
multiset v
. Optional argument n
specifies the size of
the subset to take (mset()
is a low-level helper function).
File README.Rmd
shows how to use multiset()
to
reproduce freealg::pepper()
, which gives related
functionality.
Function multinomial(v)
returns all ways of
partitioning a set into distinguishable boxes of capacities
v[1], v[2],...,v[n]
(a named vector gives more understandable
output). The number of columns is given by the multinomial
coefficient \mjeqn\sum v_i\choose
v_1\,v_2\,...\,v_nomitted.
Function allbinom(n,k)
is provided for convenience; it
enumerates the ways of choosing k
objects from n
.
These vectorized functions return a matrix whose columns are the
partitions. If this matrix is too large, consider enumerating the
partitions individually using the functionality documented in
nextpart.Rd
.
One commonly encountered idiom is blockparts(rep(n,n),n)
, which
is equivalent to compositions(n,n)
[Sloane's A001700
].
If you have a minimum number of balls in each block, a construction like
x <- c(1,1,2,1) # min y <- c(2,2,3,4) # max sweep(blockparts(y-x,sum(y)-sum(x),TRUE),1,x,"+") #> #> [1,] 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 #> [2,] 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2 #> [3,] 2 2 2 2 3 3 3 3 2 2 2 2 3 3 3 3 2 2 2 2 3 3 3 3 2 2 2 2 3 3 3 3 #> [4,] 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4
can be helpful (that is, subtract off the minimum number of balls and add them back again at the end).
blockparts(c(4,3,3,2),5) # Knuth's example, pre-fascicle 3a, p16 multiset(c(1,2,2,3)) # also Knuth
Robin K. S. Hankin
G. E. Andrews. “The theory of partitions”, Cambridge University Press, 1998
R. K. S. Hankin 2006. “Additive integer partitions in R”. Journal of Statistical Software, Volume 16, code snippet 1
R. K. S. Hankin 2007. “Urn sampling without replacement: enumerative combinatorics in R”. Journal of Statistical Software, Volume 17, code snippet 1
R. K. S. Hankin 2007. “Set partitions in R”. Journal of Statistical Software, Volume 23, code snippet 2
N. J. A. Sloane, 2008, The On-Line Encyclopedia of Integer Sequences. Sequence A001700
D. Knuth, 2004. The art of computer programming, pre-fascicle 2B “Generating all permutations”
nextpart
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.