--- title: "Integer Partitions in RcppAlgos" author: "Joseph Wood" date: "2026-03-04" output: prettydoc::html_pretty: theme: architect toc: true number_sections: false vignette: > %\VignetteIndexEntry{Integer Partitions} %\VignetteEngine{knitr::rmarkdown} %\VignetteEncoding{UTF-8} --- This document introduces integer partitions in `RcppAlgos`. An integer partition is a way of writing a number as a sum of positive integers where order does not matter. Although partitions can be expressed as constrained combinations, their additional structure allows us to employ dedicated algorithms that are far more efficient than the more general algorithms discussed in [Constraints in RcppAlgos: Constraint-Driven Combinatorial Enumeration]() The focus here is on partition-specific functionality, including classic integer partitions with repetition, distinct partitions, restricted lengths, specific multiplicities, and parallel performance. Notably, `RcppAlgos` includes a specialized algorithm for generating partitions of multisets, a case that appears to be largely absent from existing software and published literature. ------------------------------------------------------------------------ # Integer Partitions Specialized algorithms are employed when it can be determined that we are looking for [integer partitions](). As of version `2.5.0`, we now have added `partitionsGeneral` which is similar to `comboGeneral` with `constraintFun = "sum"` and `comparisonFun = "=="`. Instead of using the very general `limitConstraints` parameter, we use `target` with a default of `max(v)` as it seems more fitting for partitions. ## Standard Partitions When most folks are introduced to the subject of integer partitions, they are typically presented with the idea of breaking *N* down into parts in an unrestricted fashion. That is, parts are allowed to repeat, and the specific length is not of concern. After a few examples, partitions of a specific length are studied, followed by partitions with distinct parts, odd parts, and so on. Indeed, many textbooks present the subject in this way. In this section, we will illustrate how to attack partitions where the parts are allowed to repeat. ### Case 1: All Integer Partitions of *N* We need `v = 0:N`, `repetition = TRUE`. When we leave `m = NULL`, `m` is internally set to the length of the longest non-zero combination (this is true for all cases below). ``` 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 partitionsGeneral(0:5, repetition = TRUE) #> [,1] [,2] [,3] [,4] [,5] #> [1,] 0 0 0 0 5 #> [2,] 0 0 0 1 4 #> [3,] 0 0 0 2 3 #> [4,] 0 0 1 1 3 #> [5,] 0 0 1 2 2 #> [6,] 0 1 1 1 2 #> [7,] 1 1 1 1 1 ## Note that we could also use comboGeneral: ## comboGeneral(0:5, repetition = TRUE, ## constraintFun = "sum", ## comparisonFun = "==", limitConstraints = 5) ## ## The same goes for any of the examples below ``` ### Case 2: Integer Partitions of *N* of Length *m* Everything is the same as above except for explicitly setting the desired length and deciding whether to include zero or not. ``` r ## Including zero partitionsGeneral(0:5, 3, repetition = TRUE) #> [,1] [,2] [,3] #> [1,] 0 0 5 #> [2,] 0 1 4 #> [3,] 0 2 3 #> [4,] 1 1 3 #> [5,] 1 2 2 ## Zero not included partitionsGeneral(5, 3, repetition = TRUE) #> [,1] [,2] [,3] #> [1,] 1 1 3 #> [2,] 1 2 2 ``` ## Distinct Partitions Partitions where the parts are distinct have many interesting properties. Of note, Leonhard Euler proved that the number of partitions with distinct parts is equivalent to the number of partitions with only odd parts (See [Odd parts and distinct parts]()). We will see this in action in the section discussing [`freqs`](#using-freqs-to-refine-length). In this section, we will look at partitions where each non-zero part cannot occur more than one time. ### Case 3: Integer Partitions of *N* into Distinct Parts Same as `Case 1 & 2` except now we have `repetition = FALSE`. ``` r partitionsGeneral(0:10) #> [,1] [,2] [,3] [,4] #> [1,] 0 1 2 7 #> [2,] 0 1 3 6 #> [3,] 0 1 4 5 #> [4,] 0 2 3 5 #> [5,] 1 2 3 4 ## Zero not included and restrict the length partitionsGeneral(10, 3) #> [,1] [,2] [,3] #> [1,] 1 2 7 #> [2,] 1 3 6 #> [3,] 1 4 5 #> [4,] 2 3 5 ## Include zero and restrict the length partitionsGeneral(0:10, 3) #> [,1] [,2] [,3] #> [1,] 0 1 9 #> [2,] 0 2 8 #> [3,] 0 3 7 #> [4,] 0 4 6 #> [5,] 1 2 7 #> [6,] 1 3 6 #> [7,] 1 4 5 #> [8,] 2 3 5 ## partitions of 10 into distinct parts of every length lapply(1:4, function(x) { partitionsGeneral(10, x) }) #> [[1]] #> [,1] #> [1,] 10 #> #> [[2]] #> [,1] [,2] #> [1,] 1 9 #> [2,] 2 8 #> [3,] 3 7 #> [4,] 4 6 #> #> [[3]] #> [,1] [,2] [,3] #> [1,] 1 2 7 #> [2,] 1 3 6 #> [3,] 1 4 5 #> [4,] 2 3 5 #> #> [[4]] #> [,1] [,2] [,3] [,4] #> [1,] 1 2 3 4 ``` #### Using `freqs` to Refine Length We can utilize the `freqs` argument to obtain more distinct partitions by allowing for repeated zeros. This super optimized algorithm will only be carried out if zero is included and the number of repetitions for every number except zero is one. For example, given `v = 0:N` and `J >= 1`, if `freqs = c(J, rep(1, N))`, then the super optimized algorithm will be used, however if `freqs = c(J, 2, rep(1, N - 1))`, the general algorithm will be used. It should be noted that the general algorithms are still highly optimized so one should not fear using them. A pattern that is guaranteed to retrieve all distinct partitions of *N* is to set `v = 0:N` and `freqs = c(N, rep(1, N))` (any unused zeros beyond the maximum partition width will be omitted). For example, when `N = 10`, the first partition is returned as `0 0 0 10`, not `0 0 0 0 0 0 0 0 0 0 10`, because the maximum width is 4 in this case. ``` r ## Obtain all distinct partitions of 10 partitionsGeneral(0:10, freqs = c(10, rep(1, 10))) ## Same as c(3, rep(1, 10)) #> [,1] [,2] [,3] [,4] #> [1,] 0 0 0 10 #> [2,] 0 0 1 9 #> [3,] 0 0 2 8 #> [4,] 0 0 3 7 #> [5,] 0 0 4 6 #> [6,] 0 1 2 7 #> [7,] 0 1 3 6 #> [8,] 0 1 4 5 #> [9,] 0 2 3 5 #> [10,] 1 2 3 4 ``` #### Euler’s Theorem in Action (Odd Parts and Distinct Parts) Consider $N = 100$. The number of partitions with odd parts only is given by: ``` r sum( sapply(1:100, function(width) { partitionsCount( seq.int(1L, 99L, by = 2L), width, repetition = TRUE, target = 100 ) }) ) #> [1] 444793 ``` And now, the number of distinct parts of 100: ``` r partitionsCount(0:100, freqs = c(100, rep(1, 100))) #> [1] 444793 ``` *Et Voilà!* Note that, when generating the odd parts, we passed the vector `seq.int(1L, 99L, by = 2L)`. One might believe that, since the source vector is not of the standard form (i.e. `1:n` or `0:n`), standard partition algorithms cannot be applied. In `RcppAlgos`, we sanitize and transform the data into an isomorphic standard partition case if possible. Indeed, the non-exported function `partitionsDesign()` can be used to inspect the isomorphic standard representation used internally. ``` r ## Inspecting the partitions of 100 into odd parts of length 10 RcppAlgos:::partitionsDesign( seq.int(1L, 99L, by = 2L), 10, TRUE, target = 100, showDesign = TRUE ) #> Partition Design Overview #> ********************************************* #> #> Partitions with Repetition of width: 10 #> Partition Type: RepNoZero #> #> Is m NULL?: FALSE #> Does Soln Exist?: TRUE #> #> The isomorphic vector: #> v: 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 #> #> The first indexing vector is given by: #> startZ: 0 0 0 0 0 0 0 0 0 45 #> #> Number of partitions: 33401.000000 #> Shift: 1 #> Slope: 2 #> Mapped target: 55 #> Original target: 100 #> #> Confirm MappedTar = (Target + Width * Shift) / Slope #> 55 == (100 + 10 * 1) / 2 #> $num_partitions #> [1] 33401 #> #> $mapped_vector #> [1] 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] 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 #> #> $mapped_target #> [1] 55 #> #> $first_index_vector #> [1] 1 1 1 1 1 1 1 1 1 46 #> #> $eqn_check #> [1] TRUE #> #> $partition_type #> [1] "RepNoZero" ``` #### Caveats Using `freqs` As noted in `Case 1`, if `m = NULL`, the length of the output will be determined by the longest non-zero combination that sums to *N*. On the other hand, if the user provides `m`, that value determines the output length. ``` r ## m is NOT NULL and output has at most 2 zeros partitionsGeneral(0:10, 3, freqs = c(2, rep(1, 10))) #> [,1] [,2] [,3] #> [1,] 0 0 10 #> [2,] 0 1 9 #> [3,] 0 2 8 #> [4,] 0 3 7 #> [5,] 0 4 6 #> [6,] 1 2 7 #> [7,] 1 3 6 #> [8,] 1 4 5 #> [9,] 2 3 5 ## m is NULL and output has at most 2 zeros partitionsGeneral(0:10, freqs = c(2, rep(1, 10))) #> [,1] [,2] [,3] [,4] #> [1,] 0 0 1 9 #> [2,] 0 0 2 8 #> [3,] 0 0 3 7 #> [4,] 0 0 4 6 #> [5,] 0 1 2 7 #> [6,] 0 1 3 6 #> [7,] 0 1 4 5 #> [8,] 0 2 3 5 #> [9,] 1 2 3 4 ## m is NOT NULL, m is > maximum width, and ## more zeros than maximum width are provided partitionsGeneral(0:10, 7, freqs = c(6, rep(1, 10))) #> [,1] [,2] [,3] [,4] [,5] [,6] [,7] #> [1,] 0 0 0 0 0 0 10 #> [2,] 0 0 0 0 0 1 9 #> [3,] 0 0 0 0 0 2 8 #> [4,] 0 0 0 0 0 3 7 #> [5,] 0 0 0 0 0 4 6 #> [6,] 0 0 0 0 1 2 7 #> [7,] 0 0 0 0 1 3 6 #> [8,] 0 0 0 0 1 4 5 #> [9,] 0 0 0 0 2 3 5 #> [10,] 0 0 0 1 2 3 4 ## Similar to above, however we are missing the partition ## with part 10 as we don't have enough zeros partitionsGeneral(0:10, 8, freqs = c(6, rep(1, 10))) #> [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] #> [1,] 0 0 0 0 0 0 1 9 #> [2,] 0 0 0 0 0 0 2 8 #> [3,] 0 0 0 0 0 0 3 7 #> [4,] 0 0 0 0 0 0 4 6 #> [5,] 0 0 0 0 0 1 2 7 #> [6,] 0 0 0 0 0 1 3 6 #> [7,] 0 0 0 0 0 1 4 5 #> [8,] 0 0 0 0 0 2 3 5 #> [9,] 0 0 0 0 1 2 3 4 ## m is simply too big... we don't have enough zeros, so no results partitionsGeneral(0:10, 7, freqs = c(2, rep(1, 10))) #> [,1] [,2] [,3] [,4] [,5] [,6] [,7] ``` ## Partitions of Multisets In `RcppAlgos`, we’ve covered combinations and permutations of multisets thoroughly. This is not surprising, as these structures are well known in both academia and industry alike. The same can be said for standard and distinct partitions, which we covered above. To our knowledge, algorithms for generating partitions where each part, $p_i$, may repeat up to $r_i$ times are not readily available in combinatorics software/literature. Put simply, finding all partitions of *N* under part-specific multiplicity constraints has proven elusive. In `RcppAlgos`, however, this is no problem. ### Case 4: Integer Partitions of *N* into Parts of Varying Multiplicity ``` r ## partitions of 12 into 4 parts where each part can ## be used a specific number of times (e.g. 2 or 3) partitionsGeneral(12, 4, freqs = rep(2:3, 6)) #> [,1] [,2] [,3] [,4] #> [1,] 1 1 2 8 #> [2,] 1 1 3 7 #> [3,] 1 1 4 6 #> [4,] 1 1 5 5 #> [5,] 1 2 2 7 #> [6,] 1 2 3 6 #> [7,] 1 2 4 5 #> [8,] 1 3 3 5 #> [9,] 1 3 4 4 #> [10,] 2 2 2 6 #> [11,] 2 2 3 5 #> [12,] 2 2 4 4 #> [13,] 2 3 3 4 ``` ## Using the `table` S3 Method For both the multiset case and the distinct case with repeating zeros, we can take advantage of the `table()` S3 method. This is a natural fit for multisets, since problems are often framed in terms of multiplicities: > *Given the multiset $[p_0^{r_0}, p_1^{r_1}, \ldots, p_k^{r_k}]$, where each $p_i$ repeats $r_i$ times, find …* Without a dedicated interface, setting up `v` and `freqs` can be cumbersome, often requiring some combination of `table()`, `unique()`, `sort()`, and/or `rle()`. As of version `2.8.3`, `RcppAlgos` provides an S3 method for `table()` objects, so a multiset can be passed directly. ``` r ms = c(1,1,1,2,2,2,2,3,3,3,4,4,4,4,5,5,5,6) tab = table(ms) tab #> ms #> 1 2 3 4 5 6 #> 3 4 3 4 3 1 ## Find all partitions of 30 of length 10 under the multiplicities in `ms` head(partitionsGeneral(tab, 10, target = 30)) #> [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] #> [1,] 1 1 1 2 2 2 5 5 5 6 #> [2,] 1 1 1 2 2 3 4 5 5 6 #> [3,] 1 1 1 2 2 4 4 4 5 6 #> [4,] 1 1 1 2 2 4 4 5 5 5 #> [5,] 1 1 1 2 3 3 3 5 5 6 #> [6,] 1 1 1 2 3 3 4 4 5 6 tail(partitionsGeneral(tab, 10, target = 30)) #> [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] #> [30,] 1 2 2 2 3 3 3 4 4 6 #> [31,] 1 2 2 2 3 3 3 4 5 5 #> [32,] 1 2 2 2 3 3 4 4 4 5 #> [33,] 1 2 2 3 3 3 4 4 4 4 #> [34,] 2 2 2 2 3 3 3 4 4 5 #> [35,] 2 2 2 2 3 3 4 4 4 4 ## Find all distinct partitions of 10 (zeros supply padding capacity) partitionsGeneral(table(c(0L, 0L, 0L, 1:10))) #> [,1] [,2] [,3] [,4] #> [1,] 0 0 0 10 #> [2,] 0 0 1 9 #> [3,] 0 0 2 8 #> [4,] 0 0 3 7 #> [5,] 0 0 4 6 #> [6,] 0 1 2 7 #> [7,] 0 1 3 6 #> [8,] 0 1 4 5 #> [9,] 0 2 3 5 #> [10,] 1 2 3 4 ``` ## The Role of `target` The `target` argument specifies the integer being partitioned. That is, we are finding all ways to write `target` as a sum of elements from `v`, subject to the specified multiplicity rules. When `v` is of the standard form `0:N` or `1:N`, `target` defaults to `max(v)`, which corresponds to the classical problem of partitioning *N*. However, `target` may be set independently of `v`, allowing for more general capped or restricted partition problems. Observe: ``` r ## Here we partition 30 using only distinct parts up to 10 partitionsGeneral(10, 5, target = 30) #> [,1] [,2] [,3] [,4] [,5] #> [1,] 1 2 8 9 10 #> [2,] 1 3 7 9 10 #> [3,] 1 4 6 9 10 #> [4,] 1 4 7 8 10 #> [5,] 1 5 6 8 10 #> [6,] 1 5 7 8 9 #> [7,] 2 3 6 9 10 #> [8,] 2 3 7 8 10 #> [9,] 2 4 5 9 10 #> [10,] 2 4 6 8 10 #> [11,] 2 4 7 8 9 #> [12,] 2 5 6 7 10 #> [13,] 2 5 6 8 9 #> [14,] 3 4 5 8 10 #> [15,] 3 4 6 7 10 #> [16,] 3 4 6 8 9 #> [17,] 3 5 6 7 9 #> [18,] 4 5 6 7 8 ## Here we partition 15 using only parts up to 4 with zero included partitionsGeneral(0:4, 5, repetition = TRUE, target = 15) #> [,1] [,2] [,3] [,4] [,5] #> [1,] 0 3 4 4 4 #> [2,] 1 2 4 4 4 #> [3,] 1 3 3 4 4 #> [4,] 2 2 3 4 4 #> [5,] 2 3 3 3 4 #> [6,] 3 3 3 3 3 ## Here we partition 22 using only parts up to 8 with zero(s) included partitionsGeneral(0:8, 6, freqs = c(4, rep(1, 8)), target = 22) #> [,1] [,2] [,3] [,4] [,5] [,6] #> [1,] 0 0 1 6 7 8 #> [2,] 0 0 2 5 7 8 #> [3,] 0 0 3 4 7 8 #> [4,] 0 0 3 5 6 8 #> [5,] 0 0 4 5 6 7 #> [6,] 0 1 2 4 7 8 #> [7,] 0 1 2 5 6 8 #> [8,] 0 1 3 4 6 8 #> [9,] 0 1 3 5 6 7 #> [10,] 0 2 3 4 5 8 #> [11,] 0 2 3 4 6 7 #> [12,] 1 2 3 4 5 7 ## Same as above, just making use of the table method partitionsGeneral(table(c(rep(0L, 4), 1:8)), 6, target = 22) #> [,1] [,2] [,3] [,4] [,5] [,6] #> [1,] 0 0 1 6 7 8 #> [2,] 0 0 2 5 7 8 #> [3,] 0 0 3 4 7 8 #> [4,] 0 0 3 5 6 8 #> [5,] 0 0 4 5 6 7 #> [6,] 0 1 2 4 7 8 #> [7,] 0 1 2 5 6 8 #> [8,] 0 1 3 4 6 8 #> [9,] 0 1 3 5 6 7 #> [10,] 0 2 3 4 5 8 #> [11,] 0 2 3 4 6 7 #> [12,] 1 2 3 4 5 7 ``` ## Efficiency Generating Partitions Note, as of version `2.5.0`, one can generate partitions in parallel using the `nThreads` argument. ``` r ## partitions of 60 partitionsCount(0:60, repetition = TRUE) #> [1] 966467 ## Single threaded system.time(partitionsGeneral(0:60, repetition = TRUE)) #> user system elapsed #> 0.039 0.007 0.046 ## Using nThreads system.time(partitionsGeneral(0:60, repetition = TRUE, nThreads = 4)) #> user system elapsed #> 0.023 0.013 0.011 ## partitions of 120 into distinct parts partitionsCount(0:120, freqs = c(120, rep(1, 120))) #> [1] 2194432 system.time(partitionsGeneral(0:120, freqs = c(120, rep(1, 120)))) #> user system elapsed #> 0.017 0.004 0.020 system.time(partitionsGeneral(0:120, freqs = c(120, rep(1, 120)), nThreads = 4)) #> user system elapsed #> 0.020 0.007 0.009 ## partitions of 100 into parts of 15 with specific multiplicity partitionsCount(100, 15, freqs = rep(4:8, 20)) #> [1] 6704215 ## Over 6 million almost instantly! system.time(partitionsGeneral(100, 15, freqs = rep(4:8, 20))) #> user system elapsed #> 0.193 0.050 0.243 ```