--- title: "Integer Compositions in RcppAlgos" author: "Joseph Wood" date: "2026-03-04" output: prettydoc::html_pretty: theme: architect toc: true number_sections: false vignette: > %\VignetteIndexEntry{Integer Compositions} %\VignetteEngine{knitr::rmarkdown} %\VignetteEncoding{UTF-8} --- This document covers the topic of [integer compositions]() in `RcppAlgos`. Integer compositions are closely related to integer partitions; however, order matters. While standard compositions are well studied and widely implemented, compositions with distinct parts present additional structural constraints that require specialized treatment. To our knowledge, `RcppAlgos` is the first combinatorics library to provide a dedicated next-lexicographical algorithm for efficiently generating distinct integer compositions, enabling fast enumeration, ranking, and sampling even for large problems. ------------------------------------------------------------------------ # Integer Compositions Compositions are generated using `compositionsGeneral()`, which follows the same interface as the other combinatorial functions in `RcppAlgos`. Prior to version `2.10.0`, the composition engine in `RcppAlgos` supported only a restricted subset of compositions with repetition. Version `2.10.0` introduces complete support for compositions with repetition and adds full support for compositions with distinct parts. Planned future enhancements include comprehensive support for compositions of multisets. The output with `compositionGeneral` will be in lexicographical order. When we set `weak = TRUE` and zero is included, we will obtain ***weak compositions***, which allow for zeros to be a part of the sequence (E.g. `c(0, 0, 5), c(0, 5, 0), c(5, 0, 0)` are weak compositions of 5). As the Wikipedia article points out, we can increase the number of zeros indefinitely when `weak = TRUE`. For more general cases, we can make use of `permuteGeneral`, keeping in mind that the output will not be in lexicographical order. Another consideration with `permuteGeneral` is that when we include zero, we will always obtain weak compositions. With that in mind, generating compositions with `RcppAlgos` is easy, flexible, and quite efficient. We continue to use the `ht` function defined in the [Combination and Permutation Basics]() vignette): ``` r ht <- function(d, m = 5, n = m) { ## print the head and tail together cat("head -->\n") print(head(d, m)) cat("--------\n") cat("tail -->\n") print(tail(d, n)) } ``` ## Standard Compositions As with partitions, the standard definition of a composition allows parts to repeat and represents the most commonly encountered form. In this section we will explore compositions of this form. ### Case 1: All Compositions of *N* ``` r library(RcppAlgos) options(width = 90) packageVersion("RcppAlgos") #> [1] '2.10.0' cat(paste(capture.output(sessionInfo())[1:3], collapse = "\n")) #> R version 4.5.2 (2025-10-31) #> Platform: aarch64-apple-darwin20 #> Running under: macOS Sequoia 15.7.4 compositionsGeneral(0:3, repetition = TRUE) #> [,1] [,2] [,3] #> [1,] 0 0 3 #> [2,] 0 1 2 #> [3,] 0 2 1 #> [4,] 1 1 1 ## Weak compositions compositionsGeneral(0:3, repetition = TRUE, weak = TRUE) #> [,1] [,2] [,3] #> [1,] 0 0 3 #> [2,] 0 1 2 #> [3,] 0 2 1 #> [4,] 0 3 0 #> [5,] 1 0 2 #> [6,] 1 1 1 #> [7,] 1 2 0 #> [8,] 2 0 1 #> [9,] 2 1 0 #> [10,] 3 0 0 ## Get weak compositions with width > than target ht(compositionsGeneral(0:3, 10, repetition = TRUE, weak = TRUE)) #> head --> #> [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] #> [1,] 0 0 0 0 0 0 0 0 0 3 #> [2,] 0 0 0 0 0 0 0 0 1 2 #> [3,] 0 0 0 0 0 0 0 0 2 1 #> [4,] 0 0 0 0 0 0 0 0 3 0 #> [5,] 0 0 0 0 0 0 0 1 0 2 #> -------- #> tail --> #> [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] #> [216,] 2 0 0 0 1 0 0 0 0 0 #> [217,] 2 0 0 1 0 0 0 0 0 0 #> [218,] 2 0 1 0 0 0 0 0 0 0 #> [219,] 2 1 0 0 0 0 0 0 0 0 #> [220,] 3 0 0 0 0 0 0 0 0 0 ``` ### Case 2: Compositions of *N* of Length *m* ``` r compositionsGeneral(6, 3, repetition = TRUE) #> [,1] [,2] [,3] #> [1,] 1 1 4 #> [2,] 1 2 3 #> [3,] 1 3 2 #> [4,] 1 4 1 #> [5,] 2 1 3 #> [6,] 2 2 2 #> [7,] 2 3 1 #> [8,] 3 1 2 #> [9,] 3 2 1 #> [10,] 4 1 1 ## Including zero ht(compositionsGeneral(0:6, 3, repetition = TRUE)) #> head --> #> [,1] [,2] [,3] #> [1,] 0 0 6 #> [2,] 0 1 5 #> [3,] 0 2 4 #> [4,] 0 3 3 #> [5,] 0 4 2 #> -------- #> tail --> #> [,1] [,2] [,3] #> [12,] 2 2 2 #> [13,] 2 3 1 #> [14,] 3 1 2 #> [15,] 3 2 1 #> [16,] 4 1 1 ## Weak compositions of length 3 ht(compositionsGeneral(0:6, 3, repetition = TRUE, weak = TRUE)) #> head --> #> [,1] [,2] [,3] #> [1,] 0 0 6 #> [2,] 0 1 5 #> [3,] 0 2 4 #> [4,] 0 3 3 #> [5,] 0 4 2 #> -------- #> tail --> #> [,1] [,2] [,3] #> [24,] 4 1 1 #> [25,] 4 2 0 #> [26,] 5 0 1 #> [27,] 5 1 0 #> [28,] 6 0 0 ``` ## Distinct Compositions Distinct compositions impose the additional constraint that all parts must be unique. While conceptually simple, this restriction substantially complicates efficient generation, counting, ranking, and sampling. Version `2.10.0` introduces a next-lexicographical generation algorithm for distinct integer compositions, enabling high-performance enumeration and large-scale computations that were previously computationally prohibitive. To our knowledge, this represents the first implementation of a fully integrated next-lex engine for distinct compositions in an open-source combinatorics library. ### Case 3: Compositions of *N* into Distinct Parts ``` r compositionsGeneral(6) #> [,1] [,2] [,3] #> [1,] 1 2 3 #> [2,] 1 3 2 #> [3,] 2 1 3 #> [4,] 2 3 1 #> [5,] 3 1 2 #> [6,] 3 2 1 ht(compositionsGeneral(40, 7)) #> head --> #> [,1] [,2] [,3] [,4] [,5] [,6] [,7] #> [1,] 1 2 3 4 5 6 19 #> [2,] 1 2 3 4 5 7 18 #> [3,] 1 2 3 4 5 8 17 #> [4,] 1 2 3 4 5 9 16 #> [5,] 1 2 3 4 5 10 15 #> -------- #> tail --> #> [,1] [,2] [,3] [,4] [,5] [,6] [,7] #> [327596,] 19 6 5 4 1 3 2 #> [327597,] 19 6 5 4 2 1 3 #> [327598,] 19 6 5 4 2 3 1 #> [327599,] 19 6 5 4 3 1 2 #> [327600,] 19 6 5 4 3 2 1 ## Note the subtlety here. When zero is NOT included, the last result is ## simply the reverse of the first result. Below, this is not the case. ht(compositionsGeneral(0:40, 7)) #> head --> #> [,1] [,2] [,3] [,4] [,5] [,6] [,7] #> [1,] 0 1 2 3 4 5 25 #> [2,] 0 1 2 3 4 6 24 #> [3,] 0 1 2 3 4 7 23 #> [4,] 0 1 2 3 4 8 22 #> [5,] 0 1 2 3 4 9 21 #> -------- #> tail --> #> [,1] [,2] [,3] [,4] [,5] [,6] [,7] #> [496796,] 19 6 5 4 1 3 2 #> [496797,] 19 6 5 4 2 1 3 #> [496798,] 19 6 5 4 2 3 1 #> [496799,] 19 6 5 4 3 1 2 #> [496800,] 19 6 5 4 3 2 1 ``` #### Verifying Distinct Compositions via Partitions (Brute Force Construction) This section verifies correctness and illustrates the combinatorial overhead involved in generating distinct compositions in lexicographical order using a brute-force construction. We will use the example above of generating distinct compositions of 40 into 7 parts (including zero, non-weak case). Since we are not working with weak compositions, zero cannot appear as an ordinary part. To account for zero-padding, we proceed as follows: - Generate all distinct partitions of 40 of length 6. - Permute each partition to obtain the corresponding compositions. - `cbind` a zero column. - Repeat for partitions of length 7 (no zero padding required). - Combine and lexicographically sort the results. ``` r ## Helper: permute each partition to obtain all corresponding compositions get_perms_of_parts <- function(parts) { do.call( rbind, lapply(seq_len(nrow(parts)), \(i) permuteGeneral(table(parts[i, ]))) ) } ## Length-6 partitions become length-7 compositions by prepending one zero perms_6 <- get_perms_of_parts(partitionsGeneral(40, 6)) res_6 <- cbind(0L, perms_6) ## Length-7 partitions already match the desired output width res_7 <- get_perms_of_parts(partitionsGeneral(40, 7)) ## Combine and sort in lexicographical order res <- rbind(res_6, res_7) brute_lex <- res[do.call(order, as.data.frame(res)), ] ## Verify against the direct generator identical(compositionsGeneral(0:40, 7), brute_lex) #> [1] TRUE ``` ### Case 4: Integer Compositions of *N* into Parts of Varying Multiplicity Currently, we must use `permuteGeneral`. ``` r ## Generates error compositionsGeneral(5, 3, freqs = rep(2, 5)) #> Error: Currently, there is no composition algorithm for this case. #> Use permuteCount, permuteIter, permuteGeneral, permuteSample, or #> permuteRank instead. ## compositions of 5 into 3 parts where each part can ## be used a maximum of 2 times. permuteGeneral(5, 3, freqs = rep(2, 5), constraintFun = "sum", comparisonFun = "==", limitConstraints = 5) #> [,1] [,2] [,3] #> [1,] 1 1 3 #> [2,] 1 3 1 #> [3,] 3 1 1 #> [4,] 1 2 2 #> [5,] 2 1 2 #> [6,] 2 2 1 ``` ## Generating Compositions with `permuteGeneral()` As noted in the introduction, compositions can also be generated using `permuteGeneral()`. As with the other general combinatorial generators in `RcppAlgos`, the procedure first finds feasible combinations satisfying the constraint and then produces permutations of those combinations. In this setting, the combinations correspond to integer partitions of the target (`limitConstraints` in this case). This also implies that we always produce **weak compositions** when zero is included. Furthermore, since the results are not generated in lexicographical order, parameters such as `lower` and `upper` cannot be applied, as there is no well-defined notion of the *nth* result. For example, the following generates all weak compositions of 3 using elements from `0:3` and NOT in lex-order: ``` r ## With repetition permuteGeneral(0:3, repetition = TRUE, constraintFun = "sum", comparisonFun = "==", limitConstraints = 3) #> [,1] [,2] [,3] #> [1,] 0 0 3 #> [2,] 0 3 0 #> [3,] 3 0 0 #> [4,] 0 1 2 #> [5,] 0 2 1 #> [6,] 1 0 2 #> [7,] 1 2 0 #> [8,] 2 0 1 #> [9,] 2 1 0 #> [10,] 1 1 1 ## Similar behavior as with compositionsGeneral when width > target and ## weak = TRUE. That is, we generate more results b/c zero is included ## in the output sequences tail(permuteGeneral(0:3, 10, repetition = TRUE, constraintFun = "sum", comparisonFun = "==", limitConstraints = 3)) #> [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] #> [215,] 1 1 0 0 0 0 0 1 0 0 #> [216,] 1 1 0 0 0 0 1 0 0 0 #> [217,] 1 1 0 0 0 1 0 0 0 0 #> [218,] 1 1 0 0 1 0 0 0 0 0 #> [219,] 1 1 0 1 0 0 0 0 0 0 #> [220,] 1 1 1 0 0 0 0 0 0 0 ## Distinct Parts permuteGeneral(0:3, constraintFun = "sum", comparisonFun = "==", limitConstraints = 3) #> [,1] [,2] #> [1,] 0 3 #> [2,] 3 0 #> [3,] 1 2 #> [4,] 2 1 ## Distinct Parts and Specific Size permuteGeneral(0:3, 3, repetition = FALSE, constraintFun = "sum", comparisonFun = "==", limitConstraints = 3) #> [,1] [,2] [,3] #> [1,] 0 1 2 #> [2,] 0 2 1 #> [3,] 1 0 2 #> [4,] 1 2 0 #> [5,] 2 0 1 #> [6,] 2 1 0 ``` ## The Role of `target` Just as with integer partitions, we can make use of the `target` parameter to specify the integer being partitioned. Below, we replicate the examples from the [Integer Partitions]() vignette, this time generating compositions. Because compositions yield substantially more results, we use `ht()` to limit the displayed output. ``` r ## Here we partition 30 using only distinct parts up to 10 ht(compositionsGeneral(10, 5, target = 30)) #> head --> #> [,1] [,2] [,3] [,4] [,5] #> [1,] 1 2 8 9 10 #> [2,] 1 2 8 10 9 #> [3,] 1 2 9 8 10 #> [4,] 1 2 9 10 8 #> [5,] 1 2 10 8 9 #> -------- #> tail --> #> [,1] [,2] [,3] [,4] [,5] #> [2156,] 10 9 6 4 1 #> [2157,] 10 9 7 1 3 #> [2158,] 10 9 7 3 1 #> [2159,] 10 9 8 1 2 #> [2160,] 10 9 8 2 1 ## Here we partition 15 using only parts up to 4 with zero included ht(compositionsGeneral(0:4, 5, repetition = TRUE, target = 15)) #> head --> #> [,1] [,2] [,3] [,4] [,5] #> [1,] 0 3 4 4 4 #> [2,] 0 4 3 4 4 #> [3,] 0 4 4 3 4 #> [4,] 0 4 4 4 3 #> [5,] 1 2 4 4 4 #> -------- #> tail --> #> [,1] [,2] [,3] [,4] [,5] #> [101,] 4 4 3 1 3 #> [102,] 4 4 3 2 2 #> [103,] 4 4 3 3 1 #> [104,] 4 4 4 1 2 #> [105,] 4 4 4 2 1 ## Here we partition 22 using only parts up to 8 with zero(s) included ht(compositionsGeneral(0:8, 6, freqs = c(4, rep(1, 8)), target = 22)) #> head --> #> [,1] [,2] [,3] [,4] [,5] [,6] #> [1,] 0 0 1 6 7 8 #> [2,] 0 0 1 6 8 7 #> [3,] 0 0 1 7 6 8 #> [4,] 0 0 1 7 8 6 #> [5,] 0 0 1 8 6 7 #> -------- #> tail --> #> [,1] [,2] [,3] [,4] [,5] [,6] #> [1556,] 7 5 4 1 3 2 #> [1557,] 7 5 4 2 1 3 #> [1558,] 7 5 4 2 3 1 #> [1559,] 7 5 4 3 1 2 #> [1560,] 7 5 4 3 2 1 ## Same as above, just making use of the table method ht(compositionsGeneral(table(c(rep(0L, 4), 1:8)), 6, target = 22)) #> head --> #> [,1] [,2] [,3] [,4] [,5] [,6] #> [1,] 0 0 1 6 7 8 #> [2,] 0 0 1 6 8 7 #> [3,] 0 0 1 7 6 8 #> [4,] 0 0 1 7 8 6 #> [5,] 0 0 1 8 6 7 #> -------- #> tail --> #> [,1] [,2] [,3] [,4] [,5] [,6] #> [1556,] 7 5 4 1 3 2 #> [1557,] 7 5 4 2 1 3 #> [1558,] 7 5 4 2 3 1 #> [1559,] 7 5 4 3 1 2 #> [1560,] 7 5 4 3 2 1 ``` ## Efficiency Generating Partitions and Compositions With `compositionGeneral` we are able to take advantage of parallel computation. With `permuteGeneral`, the parallel options have no effect when generating compositions. ``` r ## compositions of 25 system.time(compositionsGeneral(0:25, repetition = TRUE)) #> user system elapsed #> 1.284 0.053 1.338 compositionsCount(0:25, repetition = TRUE) #> [1] 16777216 ## Use multiple threads for greater efficiency. Generate ## over 16 million compositions instantly system.time(compositionsGeneral(0:25, repetition = TRUE, nThreads = 4)) #> user system elapsed #> 1.471 0.061 0.410 ## weak compositions of 12 using nThreads = 4 system.time(weakComp12 <- compositionsGeneral(0:12, repetition = TRUE, weak = TRUE, nThreads = 4)) #> user system elapsed #> 0.008 0.004 0.003 ## And using permuteGeneral system.time(weakPerm12 <- permuteGeneral(0:12, 12, repetition = TRUE, constraintFun = "sum", comparisonFun = "==", limitConstraints = 12)) #> user system elapsed #> 0.009 0.002 0.011 dim(weakPerm12) #> [1] 1352078 12 identical(weakPerm12[do.call(order, as.data.frame(weakPerm12)), ], weakComp12) #> [1] TRUE ## Distinct Parts system.time(compositionsGeneral(55, 8)) #> user system elapsed #> 0.626 0.017 0.642 compositionsCount(55, 8) #> [1] 14192640 ## Similar to above... using 4 threads gets us the result instantly system.time(compositionsGeneral(55, 8, nThreads = 4)) #> user system elapsed #> 0.645 0.017 0.189 ## General compositions with varying multiplicities system.time(comp25_gen <- permuteGeneral(25, 10, freqs = rep(4:8, 5), constraintFun = "sum", comparisonFun = "==", limitConstraints = 25)) #> user system elapsed #> 0.013 0.004 0.018 dim(comp25_gen) #> [1] 946092 10 ```