R/genComp.R
genComp.RdThis function will return either all, or a length restricted subset of the integer partitions of an integer n. The method works by considering compositions rather than partions, hence the name.
genComp(n, len = TRUE, addZeros = FALSE)A positive non-zero integer
Either logical TRUE, or a positive integer. If the latter
form is used then only those partions of length less than or equal to len
are returned. If len is greater than or equal to n then all
partitions are returned.
If true then each partition is padded with zeros to length
len, or to length n if len is TRUE.
A list with each list element representing an integer partition
This function will return all partions, or a subset, of an integer n. It
makes no check to see if this is a sensible thing to do. It also does it in
a lazy way in that in the restricted case it generates all partitions and
then only returns those that satistfy the length constraint. Users are
advised to check how many partitions are possible using partition number
function which is implemented the P function in the partions
package. Having said this P(50) is approximately 200 thousand, and P(100)
around 190 million, so the function should work well for smallish n.
This function does not warn the user that the requested set of partitions may be very large. In addition, all working is handled entirely in memory, and so this may cause it to crash if the request is execeptionally large.
Kelleher, J. (2005), Encoding Partitions As Ascending Compositions, PhD thesis, University College Cork.
Kelleher, J. and O'Sullivan, B. (2009), Generating All Partitions: A Comparison Of Two Encodings, doi:10.48550/arXiv.0909.2331 .
Kelleher, J. (2014) Generating Integer Partitions. Blog post, no longer
online. Its Python function accel_asc, from which the C++ code in
this package was ported, is included with the package:
system.file("python", "accel_asc.py", package = "multicool").
## a small numeric example with all 11 partitions of 6
genComp(6)
#> [[1]]
#> [1] 1 1 1 1 1 1
#>
#> [[2]]
#> [1] 1 1 1 1 2
#>
#> [[3]]
#> [1] 1 1 1 3
#>
#> [[4]]
#> [1] 1 1 2 2
#>
#> [[5]]
#> [1] 1 1 4
#>
#> [[6]]
#> [1] 1 2 3
#>
#> [[7]]
#> [1] 1 5
#>
#> [[8]]
#> [1] 2 2 2
#>
#> [[9]]
#> [1] 2 4
#>
#> [[10]]
#> [1] 3 3
#>
#> [[11]]
#> [1] 6
#>
## a small example with the integer partitions of 6 of length 3 with empty partitions added
genComp(6, 3, TRUE)
#> [[1]]
#> [1] 1 1 4
#>
#> [[2]]
#> [1] 1 2 3
#>
#> [[3]]
#> [1] 1 5 0
#>
#> [[4]]
#> [1] 2 2 2
#>
#> [[5]]
#> [1] 2 4 0
#>
#> [[6]]
#> [1] 3 3 0
#>
#> [[7]]
#> [1] 6 0 0
#>
## a larger example - 627 partions of 20, but restricted to those of length 3 or smaller
genComp(20, 3)
#> [[1]]
#> [1] 1 1 18
#>
#> [[2]]
#> [1] 1 2 17
#>
#> [[3]]
#> [1] 1 3 16
#>
#> [[4]]
#> [1] 1 4 15
#>
#> [[5]]
#> [1] 1 5 14
#>
#> [[6]]
#> [1] 1 6 13
#>
#> [[7]]
#> [1] 1 7 12
#>
#> [[8]]
#> [1] 1 8 11
#>
#> [[9]]
#> [1] 1 9 10
#>
#> [[10]]
#> [1] 1 19
#>
#> [[11]]
#> [1] 2 2 16
#>
#> [[12]]
#> [1] 2 3 15
#>
#> [[13]]
#> [1] 2 4 14
#>
#> [[14]]
#> [1] 2 5 13
#>
#> [[15]]
#> [1] 2 6 12
#>
#> [[16]]
#> [1] 2 7 11
#>
#> [[17]]
#> [1] 2 8 10
#>
#> [[18]]
#> [1] 2 9 9
#>
#> [[19]]
#> [1] 2 18
#>
#> [[20]]
#> [1] 3 3 14
#>
#> [[21]]
#> [1] 3 4 13
#>
#> [[22]]
#> [1] 3 5 12
#>
#> [[23]]
#> [1] 3 6 11
#>
#> [[24]]
#> [1] 3 7 10
#>
#> [[25]]
#> [1] 3 8 9
#>
#> [[26]]
#> [1] 3 17
#>
#> [[27]]
#> [1] 4 4 12
#>
#> [[28]]
#> [1] 4 5 11
#>
#> [[29]]
#> [1] 4 6 10
#>
#> [[30]]
#> [1] 4 7 9
#>
#> [[31]]
#> [1] 4 8 8
#>
#> [[32]]
#> [1] 4 16
#>
#> [[33]]
#> [1] 5 5 10
#>
#> [[34]]
#> [1] 5 6 9
#>
#> [[35]]
#> [1] 5 7 8
#>
#> [[36]]
#> [1] 5 15
#>
#> [[37]]
#> [1] 6 6 8
#>
#> [[38]]
#> [1] 6 7 7
#>
#> [[39]]
#> [1] 6 14
#>
#> [[40]]
#> [1] 7 13
#>
#> [[41]]
#> [1] 8 12
#>
#> [[42]]
#> [1] 9 11
#>
#> [[43]]
#> [1] 10 10
#>
#> [[44]]
#> [1] 20
#>