Nothing
Integer Compositions in RcppAlgos
In RcppAlgos: High Performance Tools for Combinatorics and Computational Mathematics
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):
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
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
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
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.
## 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.
## 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:
## 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.
## 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.
## 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
Try the RcppAlgos package in your browser
Any scripts or data that you put into this service are public.
RcppAlgos documentation built on March 8, 2026, 9:08 a.m.
R Package Documentation
Browse R Packages
We want your feedback!
Note that we can't provide technical support on individual packages. You should contact the package authors for that.
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):
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
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
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
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.
cbinda zero column.- Repeat for partitions of length 7 (no zero padding required).
- Combine and lexicographically sort the results.
## 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.
## 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:
## 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.
## 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.
## 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
Try the RcppAlgos package in your browser
Any scripts or data that you put into this service are public.
R Package Documentation
Browse R Packages
We want your feedback!
Note that we can't provide technical support on individual packages. You should contact the package authors for that.
Embedding an R snippet on your website
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.