RcppAlgos provides high-performance algorithms for working with combinatorial objects in R. It includes efficient implementations for combinations, permutations, integer partitions, and compositions, with support for multisets, constraints, and extremely large search spaces through memory-efficient iterators.
The package also implements specialized algorithms for problems rarely supported by other combinatorics libraries, including partitions of multisets, partitions of groups, and order-invariant Cartesian products. Many routines support ranking and unranking, parallel computation, and reproducible sampling. The package also includes fast prime number utilities built on the excellent work of Kim Walisch.
Key Features
- High-performance generation of combinations and permutations
- Integer partitions and compositions under flexible constraints
- Support for multisets and restricted combinatorial structures
- Memory-efficient iterators for exploring very large combinatorial spaces
- Ranking and unranking algorithms
- Parallel computation support
- Fast prime number utilities:
-
primeSievefor generating primes -
primeCountfor counting primes using Legendre’s formula -
primeFactorizefor prime factorization
-
RcppAlgos is designed to handle combinatorial problems ranging from small enumerations to extremely large search spaces where generating all results at once would be impractical.
What Makes RcppAlgos Unique
RcppAlgos implements several combinatorial algorithms that are uncommon or unavailable in most R libraries, including:
- partitions of multisets
- partitions of groups (
comboGroups) - order-invariant Cartesian products (
comboGrid) - compositions with distinct parts
Installation
install.packages("RcppAlgos")
## install the development version
devtools::install_github("jwood000/RcppAlgos")Usage
Combinatorics Basics
## Find all 3-tuples combinations of 1:4
comboGeneral(4, 3)
#> [,1] [,2] [,3]
#> [1,] 1 2 3
#> [2,] 1 2 4
#> [3,] 1 3 4
#> [4,] 2 3 4
## Alternatively, iterate over combinations
a <- comboIter(4, 3)
a@nextIter()
#> [1] 1 2 3
a@back()
#> [1] 2 3 4
a[[2]]
#> [1] 1 2 4
## Pass any atomic type vector
permuteGeneral(letters, 3, upper = 4)
#> [,1] [,2] [,3]
#> [1,] "a" "b" "c"
#> [2,] "a" "b" "d"
#> [3,] "a" "b" "e"
#> [4,] "a" "b" "f"
## Generate a reproducible sample
comboSample(10, 8, TRUE, n = 5, seed = 84)
#> [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,] 3 3 3 6 6 10 10 10
#> [2,] 1 3 3 4 4 7 9 10
#> [3,] 3 7 7 7 9 10 10 10
#> [4,] 3 3 3 9 10 10 10 10
#> [5,] 1 2 2 3 3 4 4 7Integer Partitions and Compositions
## Flexible partitioning algorithms
partitionsGeneral(0:5, 3, freqs = rep(1:2, 3), target = 6)
#> [,1] [,2] [,3]
#> [1,] 0 1 5
#> [2,] 0 2 4
#> [3,] 0 3 3
#> [4,] 1 1 4
#> [5,] 1 2 3
## And compositions
compositionsGeneral(0:3, repetition = TRUE)
#> [,1] [,2] [,3]
#> [1,] 0 0 3
#> [2,] 0 1 2
#> [3,] 0 2 1
#> [4,] 1 1 1
## Get combinations such that the product is between
## 3600 and 4000 (including 3600 but not 4000)
comboGeneral(5, 7, TRUE, constraintFun = "prod",
comparisonFun = c(">=","<"),
limitConstraints = c(3600, 4000),
keepResults = TRUE)
#> [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,] 1 2 3 5 5 5 5 3750
#> [2,] 1 3 3 4 4 5 5 3600
#> [3,] 1 3 4 4 4 4 5 3840
#> [4,] 2 2 3 3 4 5 5 3600
#> [5,] 2 2 3 4 4 4 5 3840
#> [6,] 3 3 3 3 3 3 5 3645
#> [7,] 3 3 3 3 3 4 4 3888
## We can also iterate over constrained cases. This is useful when we do not
## know the total number of results upfront, while still avoiding the cost of
## generating the full result set in memory.
p <- permuteIter(
5, 7, TRUE,
constraintFun = "prod",
comparisonFun = c(">=", "<"),
limitConstraints = c(3600, 4000)
)
p@nextIter()
#> [1] 1 2 3 5 5 5 5Cartesian Products
## Base R expand.grid returns a data.frame by default
## and varies the first column the fastest
bR <- expand.grid(rep(list(1:3), 3))
head(bR, n = 3)
#> Var1 Var2 Var3
#> 1 1 1 1
#> 2 2 1 1
#> 3 3 1 1
## RcppAlgos::expandGrid returns a matrix if the input is of the same class,
## otherwise it returns a data.frame. Also varies the first column the slowest.
algos <- expandGrid(rep(list(1:3), 3))
head(algos, n = 3)
#> Var1 Var2 Var3
#> [1,] 1 1 1
#> [2,] 1 1 2
#> [3,] 1 1 3
## With RcppAlgos::comboGrid order doesn't matter, so c(1, 1, 2),
## c(1, 2, 1), and c(2, 1, 1) are the same.
comboGrid(rep(list(1:3), 3))
#> Var1 Var2 Var3
#> [1,] 1 1 1
#> [2,] 1 1 2
#> [3,] 1 1 3
#> [4,] 1 2 2
#> [5,] 1 2 3
#> [6,] 1 3 3
#> [7,] 2 2 2
#> [8,] 2 2 3
#> [9,] 2 3 3
#> [10,] 3 3 3Partitions of Groups
Efficiently partition a vector into groups with comboGroups. For example, the code below finds all possible partitions into groups of size 2 and 3. See this Stack Overflow post:
Find all possible team pairing schemes
players <- c("Ross", "Bobby", "Max", "Casper", "Jake")
comboGroups(players, grpSizes = c(2, 3))
#> Grp1 Grp1 Grp2 Grp2 Grp2
#> [1,] "Ross" "Bobby" "Max" "Casper" "Jake"
#> [2,] "Ross" "Max" "Bobby" "Casper" "Jake"
#> [3,] "Ross" "Casper" "Bobby" "Max" "Jake"
#> [4,] "Ross" "Jake" "Bobby" "Max" "Casper"
#> [5,] "Bobby" "Max" "Ross" "Casper" "Jake"
#> [6,] "Bobby" "Casper" "Ross" "Max" "Jake"
#> [7,] "Bobby" "Jake" "Ross" "Max" "Casper"
#> [8,] "Max" "Casper" "Ross" "Bobby" "Jake"
#> [9,] "Max" "Jake" "Ross" "Bobby" "Casper"
#> [10,] "Casper" "Jake" "Ross" "Bobby" "Max"Computational Mathematics
## Generate prime numbers
primeSieve(50)
#> [1] 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
## Many of the functions can produce results in
## parallel for even greater performance
p <- primeSieve(1e15, 1e15 + 1e8, nThreads = 4)
head(p)
#> [1] 1000000000000037 1000000000000091 1000000000000159
#> [4] 1000000000000187 1000000000000223 1000000000000241
tail(p)
#> [1] 1000000099999847 1000000099999867 1000000099999907
#> [4] 1000000099999919 1000000099999931 1000000099999963
## Count prime numbers less than n
primeCount(1e10)
#> [1] 455052511
## Get the prime factorization
set.seed(24028)
primeFactorize(sample(1e15, 3), namedList = TRUE)
#> $`701030825091514`
#> [1] 2 149 2352452433193
#>
#> $`83054168594779`
#> [1] 3098071 26808349
#>
#> $`397803024735610`
#> [1] 2 5 13 13 235386405169Further Reading
- Function Documentation
- Computational Mathematics Overview
- Combination and Permutation Basics
- Integer Partitions in RcppAlgos
- Integer Compositions in RcppAlgos
- Combinatorial Sampling
- Constraints in RcppAlgos: Constraint-Driven Combinatorial Enumeration
- Attacking Problems Related to the Subset Sum Problem
- Combinatorial Iterators in RcppAlgos
- Cartesian Products and Partitions of Groups
Why RcppAlgos but no Rcpp?
Earlier versions of RcppAlgos relied on Rcpp to interface C++ with R. The current implementation uses cpp11, which provides a lightweight interface to R’s C API. While the package no longer depends on Rcpp, the project owes much to the excellent work of the Rcpp community.
Contact
If you would like to report a bug, have a question, or have suggestions for possible improvements, please file an issue.