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.
primeSieve for generating primesprimeCount for counting primes using Legendre’s
formulaprimeFactorize for prime factorizationRcppAlgos is designed to handle combinatorial problems ranging from small enumerations to extremely large search spaces where generating all results at once would be impractical.
RcppAlgos
UniqueRcppAlgos implements several combinatorial algorithms that are uncommon or unavailable in most R libraries, including:
comboGroups)comboGrid)Detailed benchmarks can be found here:
install.packages("RcppAlgos")
## install the development version
devtools::install_github("jwood000/RcppAlgos")## 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 7## 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 5## 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 3Efficiently 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"## 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 235386405169RcppAlgos 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.
If you would like to report a bug, have a question, or have suggestions for possible improvements, please file an issue.