Integer Partitions in RcppAlgos
Joseph Wood
2026-03-04
Source:vignettes/IntegerPartitions.Rmd
IntegerPartitions.RmdThis 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).
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 belowCase 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.
## 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 2Distinct 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.
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.
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 4Using 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.
## 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 4Euler’s Theorem in Action (Odd Parts and Distinct Parts)
Consider . The number of partitions with odd parts only is given by:
sum(
sapply(1:100, function(width) {
partitionsCount(
seq.int(1L, 99L, by = 2L), width,
repetition = TRUE, target = 100
)
})
)
#> [1] 444793And now, the number of distinct parts of 100:
partitionsCount(0:100, freqs = c(100, rep(1, 100)))
#> [1] 444793Et 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.
## 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.
## 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,
,
may repeat up to
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
## 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 4Using 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 , where each repeats 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.
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 4The 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:
## 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 7Efficiency Generating Partitions
Note, as of version 2.5.0, one can generate partitions
in parallel using the nThreads argument.
## 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