parts: Enumerate the partitions of an integer In partitions: Additive Partitions of Integers

Description

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.

Usage

 1 2 3 4 5 6 7 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) 

Arguments

 n 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 exactly m parts; and TRUE meaning to include partitions of n into at most m parts (because zero parts are included) include.fewer In function blockparts(), Boolean with default FALSE meaning to return vectors whose sum is exactly n and TRUE meaning to return partitions whose sum is at most n 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 v In function multiset(), an integer vector representing a multiset. Argument n is the size of the sample to be taken

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 \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() returns all ways of ordering a multiset (mset() is a low-level helper function).

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 > parts(7) [1,] 7 6 5 5 4 4 4 3 3 3 3 2 2 2 1 [2,] 0 1 2 1 3 2 1 3 2 2 1 2 2 1 1 [3,] 0 0 0 1 0 1 1 1 2 1 1 2 1 1 1 [4,] 0 0 0 0 0 0 1 0 0 1 1 1 1 1 1 [5,] 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 [6,] 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 [7,] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 > P(7) [1] 15 > diffparts(9) [1,] 9 8 7 6 6 5 5 4 [2,] 0 1 2 3 2 4 3 3 [3,] 0 0 0 0 1 0 1 2 > Q(9) [1] 8 > restrictedparts(9,4) [1,] 9 8 7 6 5 7 6 5 4 5 4 3 6 5 4 4 3 3 [2,] 0 1 2 3 4 1 2 3 4 2 3 3 1 2 3 2 3 2 [3,] 0 0 0 0 0 1 1 1 1 2 2 3 1 1 1 2 2 2 [4,] 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 2 > R(4,9,include.zero=TRUE) [1] 18 > blockparts(1:4,5) [1,] 1 1 0 1 1 0 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 0 [2,] 2 1 2 2 1 2 0 1 2 1 2 0 1 0 1 2 0 1 0 0 1 0 [3,] 2 3 3 1 2 2 3 3 0 1 1 2 2 3 0 0 1 1 2 0 0 1 [4,] 0 0 0 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 4 4 4 > S(1:4,5) [1] 22 > compositions(5,3) [1,] 5 4 3 2 1 0 4 3 2 1 0 3 2 1 0 2 1 0 1 0 0 [2,] 0 1 2 3 4 5 0 1 2 3 4 0 1 2 3 0 1 2 0 1 0 [3,] 0 0 0 0 0 0 1 1 1 1 1 2 2 2 2 3 3 3 4 4 5 > S(rep(5,3),5) [1] 21 > setparts(4) [1,] 1 1 1 1 2 1 1 1 1 1 1 2 2 2 1 [2,] 1 1 1 2 1 2 1 2 2 1 2 1 1 3 2 [3,] 1 2 1 1 1 2 2 1 3 2 1 3 1 1 3 [4,] 1 1 2 1 1 1 2 2 1 3 3 1 3 1 4 > setparts(c(1,2,2)) [1,] 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 [2,] 2 2 3 1 1 1 2 2 3 2 2 3 1 1 1 [3,] 3 2 2 3 2 2 1 1 1 3 2 2 2 1 2 [4,] 2 3 2 2 3 2 3 2 2 1 1 1 2 2 1 [5,] 1 1 1 2 2 3 2 3 2 2 3 2 1 2 2 

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].

If you have a minimum number of balls in each block, a construction like

 1 2 3 4 5  x <- c(1,1,2,1) # min y <- c(2,3,4,5) # max sweep(blockparts(y-x,7-sum(x)),1,x,"+") 

can be helpful (that is, subtract off the minimum number of balls and add them back again at the end).

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

• 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

Examples

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 parts(5) diffparts(10) matplot(t(diffparts(27)),type='l',lty=1) restrictedparts(9,4) restrictedparts(9,4,FALSE) restrictedparts(9,4,decreasing=TRUE) blockparts(1:4) blockparts(1:4,3) blockparts(1:4,3,include.fewer=TRUE) blockparts(c(4,3,3,2),5) # Knuth's example, pre-fascicle 3a, p16 compositions(4) # not the same as parts(4) compositions(4,4) # With 10 blocks, enumerate all partitions with maxima of 1:5 and minima # of c(0,1,1,2,1): a <- c(0,1,1,2,1) sweep(blockparts(1:5-a,10-sum(a)),1,a,"+") #Knuth's example: multiset(c(1,2,2,3)) multiset(rep(4+1:3,1:3),3) 

Example output


[1,] 5 4 3 3 2 2 1
[2,] 0 1 2 1 2 1 1
[3,] 0 0 0 1 1 1 1
[4,] 0 0 0 0 0 1 1
[5,] 0 0 0 0 0 0 1

[1,] 10 9 8 7 7 6 6 5 5 4
[2,]  0 1 2 3 2 4 3 4 3 3
[3,]  0 0 0 0 1 0 1 1 2 2
[4,]  0 0 0 0 0 0 0 0 0 1

[1,] 9 8 7 6 5 7 6 5 4 5 4 3 6 5 4 4 3 3
[2,] 0 1 2 3 4 1 2 3 4 2 3 3 1 2 3 2 3 2
[3,] 0 0 0 0 0 1 1 1 1 2 2 3 1 1 1 2 2 2
[4,] 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 2

[1,] 6 5 4 4 3 3
[2,] 1 2 3 2 3 2
[3,] 1 1 1 2 2 2
[4,] 1 1 1 1 1 2

[1,] 9 8 7 6 5 7 6 5 4 5 4 3 6 5 4 4 3 3
[2,] 0 1 2 3 4 1 2 3 4 2 3 3 1 2 3 2 3 2
[3,] 0 0 0 0 0 1 1 1 1 2 2 3 1 1 1 2 2 2
[4,] 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 2

[1,] 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
[2,] 0 0 1 1 2 2 0 0 1 1 2 2 0 0 1 1 2 2 0 0 1 1 2 2 0 0 1 1 2 2 0 0 1 1 2 2 0
[3,] 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 0 0 0 0 0 0 1 1 1 1 1 1 2
[4,] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1

[1,] 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
[2,] 0 1 1 2 2 0 0 1 1 2 2 0 0 1 1 2 2 0 0 1 1 2 2 0 0 1 1 2 2 0 0 1 1 2 2 0 0
[3,] 2 2 2 2 2 3 3 3 3 3 3 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 0 0
[4,] 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3

[1,] 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
[2,] 1 1 2 2 0 0 1 1 2 2 0 0 1 1 2 2 0 0 1 1 2 2 0 0 1 1 2 2 0 0 1 1 2 2 0 0 1
[3,] 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2
[4,] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4

[1,] 1 0 1 0 1 0 1 0 1
[2,] 1 2 2 0 0 1 1 2 2
[3,] 2 2 2 3 3 3 3 3 3
[4,] 4 4 4 4 4 4 4 4 4

[1,] 1 1 0 1 0 0 1 0 1 0 0 1 0 0 0
[2,] 2 1 2 0 1 0 1 2 0 1 0 0 1 0 0
[3,] 0 1 1 2 2 3 0 0 1 1 2 0 0 1 0
[4,] 0 0 0 0 0 0 1 1 1 1 1 2 2 2 3

[1,] 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0
[2,] 0 0 1 1 2 2 0 0 1 1 2 0 0 1 0 0 0 1 1 2 0 0 1 0 0 0 1 0 0
[3,] 0 0 0 0 0 0 1 1 1 1 1 2 2 2 3 0 0 0 0 0 1 1 1 2 0 0 0 1 0
[4,] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 2 3

[1,] 4 3 2 4 3 2 1 3 2 1 0 2 1 0 4 3 2 1 3 2 1 0 2 1 0 1 0 3 2 1 0 2 1 0 1 0 0
[2,] 1 2 3 0 1 2 3 0 1 2 3 0 1 2 0 1 2 3 0 1 2 3 0 1 2 0 1 0 1 2 3 0 1 2 0 1 0
[3,] 0 0 0 1 1 1 1 2 2 2 2 3 3 3 0 0 0 0 1 1 1 1 2 2 2 3 3 0 0 0 0 1 1 1 2 2 3
[4,] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2

[1,] 4 1 2 1 3 1 2 1
[2,] 0 3 2 1 1 2 1 1
[3,] 0 0 0 2 0 1 1 1
[4,] 0 0 0 0 0 0 0 1

[1,] 4 3 2 1 0 3 2 1 0 2 1 0 1 0 0 3 2 1 0 2 1 0 1 0 0 2 1 0 1 0 0 1 0 0 0
[2,] 0 1 2 3 4 0 1 2 3 0 1 2 0 1 0 0 1 2 3 0 1 2 0 1 0 0 1 2 0 1 0 0 1 0 0
[3,] 0 0 0 0 0 1 1 1 1 2 2 2 3 3 4 0 0 0 0 1 1 1 2 2 3 0 0 0 1 1 2 0 0 1 0
[4,] 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 4

[1,] 1 1 1 0 1 1 1 0 1 1 0 0 1 1 0 1 1 0 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 0
[2,] 2 2 1 2 2 2 1 2 2 1 2 1 2 1 2 2 1 2 1 1 2 1 2 1 2 1 1 2 1 1 1 2 1 1
[3,] 3 2 3 3 3 2 3 3 1 2 2 3 2 3 3 1 2 2 3 1 1 2 1 2 2 3 1 1 2 1 1 1 2 1
[4,] 3 4 4 4 2 3 3 3 4 4 4 4 2 2 2 3 3 3 3 4 4 4 2 2 2 2 3 3 3 4 2 2 2 3
[5,] 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5

[1,] 1 1 1 2 2 2 2 2 2 3 3 3
[2,] 2 2 3 1 1 2 2 3 3 1 2 2
[3,] 2 3 2 2 3 1 3 1 2 2 1 2
[4,] 3 2 2 3 2 3 1 2 1 2 2 1

[1,] 5 6 6 5 5 6 6 7 7 6 6 7 5 7 7 6 7 7 7
[2,] 6 5 6 6 7 5 7 5 6 6 7 6 7 5 7 7 6 7 7
[3,] 6 6 5 7 6 7 5 6 5 7 6 6 7 7 5 7 7 6 7


partitions documentation built on Feb. 23, 2021, 5:06 p.m.