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.
Integer to be partitioned. In function blockparts(),
the default of NULL means to return all partitions of any size
m
In functions restrictedparts() and
compositions(), the order of the partition
include.zero
In functions restrictedparts() and
compositions(), Boolean with default FALSE meaning to
include only partitions of n into exactlym
parts; and TRUE meaning to include partitions of n into
at mostm parts (because zero parts are included)
include.fewer
In function blockparts(), Boolean with
default FALSE meaning to return vectors whose sum is
exactlyn and TRUE meaning to return partitions
whose sum is at mostn
decreasing
In restrictedparts(), Boolean with default
TRUE meaning to return partitions whose parts are in
decreasing order and FALSE meaning to return partitions in
lexicographical order, as appearing in Hindenburg's
algorithm. Note that setting to decreasing to FALSE
has the effect of making conjugate() return garbage
f
In function blockparts(), a vector of strictly
positive integers that gives the maximal number of blocks; see
details
Details
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).
If m>n, the partitions are padded with zeros.
Function blockparts() enumerates the compositions of an
integer subject to a maximum criterion: given vector
y=(y_1,...,y_p) all sets of
a=(a_1,...,a_p) satisfying
sum(a_i)=n subject to 0 <= 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 sum(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.
Function compositions() returns all
2^(n-1) ways of partitioning an integer; thus
4+1+1 is distinct from 1+4+1 or 1+1+4. 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.
Note
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].
Author(s)
Robin K. S. Hankin
References
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