A collection of high performance functions and iterators implemented in C++ for solving problems in combinatorics and computational mathematics.
{combo|permute}General
: Generate all
combinations/permutations of a vector (including multisets) meeting
specific criteria.{partitions|compositions}General
:
Efficient algorithms for partitioning numbers under various
constraints{combo|permute|partitions|compositions}Sample
:
Generate reproducible random samples{combo|permute|partitions|compositions}Iter
:
Flexible iterators allow for bidirectional iteration as well as random
access.primeSieve
: Fast prime number
generatorprimeCount
: Prime counting function
using Legendre’s
formulaThe primeSieve
function and the primeCount
function are both based off of the excellent work by Kim Walisch. The respective
repos can be found here: kimwalisch/primesieve;
kimwalisch/primecount
Additionally, many of the sieving functions make use of the fast integer division library libdivide by ridiculousfish.
install.packages("RcppAlgos")
## install the development version
::install_github("jwood000/RcppAlgos") devtools
## 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
= comboIter(4, 3)
a @nextIter()
a#> [1] 1 2 3
@back()
a#> [1] 2 3 4
2]]
a[[#> [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"
## 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
## 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
## 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 even iterate over constrained cases. These are
## great when we don't know how many results there are upfront.
## Save on memory and still at the speed of C++!!
= permuteIter(5, 7, TRUE, constraintFun = "prod",
p comparisonFun = c(">=","<"),
limitConstraints = c(3600, 4000),
keepResults = TRUE)
## Get the next n results
<- p@nextNIter(1048)
t
## N.B. keepResults = TRUE adds the 8th column
tail(t)
#> [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1043,] 5 4 4 3 4 1 4 3840
#> [1044,] 5 4 4 3 4 4 1 3840
#> [1045,] 5 4 4 4 1 3 4 3840
#> [1046,] 5 4 4 4 1 4 3 3840
#> [1047,] 5 4 4 4 3 1 4 3840
#> [1048,] 5 4 4 4 3 4 1 3840
## Continue iterating from where we left off
@nextIter()
p#> [1] 5 4 4 4 4 1 3 3840
@nextIter()
p#> [1] 5 4 4 4 4 3 1 3840
@nextIter()
p#> [1] 2 2 3 3 4 5 5 3600
## N.B. totalResults and totalRemaining are NA because there is no
## closed form solution for determining this.
@summary()
p#> $description
#> [1] "Permutations with repetition of 5 choose 7 where the prod is between 3600 and 4000"
#>
#> $currentIndex
#> [1] 1051
#>
#> $totalResults
#> [1] NA
#>
#> $totalRemaining
#> [1] NA
## 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
= primeSieve(1e15, 1e15 + 1e8, nThreads = 4)
p
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 235386405169
RcppAlgos
but no
Rcpp
?Previous versions of RcppAlgos
relied on Rcpp to ease the burden of
exposing C++ to R. While the current version of RcppAlgos
does not utilize Rcpp
, it would not be possible without the
myriad of excellent contributions to Rcpp
.
If you would like to report a bug, have a question, or have suggestions for possible improvements, please file an issue.