comboGeneral {RcppAlgos} | R Documentation |
Generate Combinations and Permutations of a Vector with/without Constraints
Description
Generate combinations or permutations of a vector with or without constraints.
Produce results in parallel using the
Parallel
ornThreads
arguments. You can also apply each of the five compiled functions given by the argumentconstraintFun
in parallel.The arguments
lower
andupper
make it possible to generate combinations/permutations in chunks allowing for parallelization via theparallel-package
. This is convenient when you want to apply a custom function to the output in parallel.Attack integer partition and general subset sum problems.
GMP support allows for exploration of combinations/permutations of vectors with many elements.
The output is in lexicographical order.
Usage
comboGeneral(v, m = NULL, ...)
permuteGeneral(v, m = NULL, ...)
## S3 method for class 'numeric'
comboGeneral(v, m = NULL, repetition = FALSE, freqs = NULL,
lower = NULL, upper = NULL, constraintFun = NULL,
comparisonFun = NULL, limitConstraints = NULL,
keepResults = NULL, FUN = NULL, Parallel = FALSE,
nThreads = NULL, tolerance = NULL, FUN.VALUE = NULL, ...)
## S3 method for class 'numeric'
permuteGeneral(v, m = NULL, repetition = FALSE, freqs = NULL,
lower = NULL, upper = NULL, constraintFun = NULL,
comparisonFun = NULL, limitConstraints = NULL,
keepResults = NULL, FUN = NULL, Parallel = FALSE,
nThreads = NULL, tolerance = NULL, FUN.VALUE = NULL, ...)
## S3 method for class 'factor'
comboGeneral(
v, m = NULL, repetition = FALSE, freqs = NULL, lower = NULL, upper = NULL,
FUN = NULL, Parallel = FALSE, nThreads = NULL, FUN.VALUE = NULL, ...
)
## S3 method for class 'factor'
permuteGeneral(
v, m = NULL, repetition = FALSE, freqs = NULL, lower = NULL, upper = NULL,
FUN = NULL, Parallel = FALSE, nThreads = NULL, FUN.VALUE = NULL, ...
)
## Default S3 method:
comboGeneral(v, m = NULL, repetition = FALSE,
freqs = NULL, lower = NULL, upper = NULL,
FUN = NULL, FUN.VALUE = NULL, ...)
## Default S3 method:
permuteGeneral(v, m = NULL, repetition = FALSE,
freqs = NULL, lower = NULL, upper = NULL,
FUN = NULL, FUN.VALUE = NULL, ...)
## S3 method for class 'table'
comboGeneral(
v, m = NULL, lower = NULL, upper = NULL, constraintFun = NULL,
comparisonFun = NULL, limitConstraints = NULL, keepResults = NULL,
FUN = NULL, Parallel = FALSE, nThreads = NULL, tolerance = NULL,
FUN.VALUE = NULL, ...
)
## S3 method for class 'table'
permuteGeneral(
v, m = NULL, lower = NULL, upper = NULL, constraintFun = NULL,
comparisonFun = NULL, limitConstraints = NULL, keepResults = NULL,
FUN = NULL, Parallel = FALSE, nThreads = NULL, tolerance = NULL,
FUN.VALUE = NULL, ...
)
## S3 method for class 'list'
comboGeneral(v, m = NULL, repetition = FALSE,
freqs = NULL, lower = NULL, upper = NULL, ...)
## S3 method for class 'list'
permuteGeneral(v, m = NULL, repetition = FALSE,
freqs = NULL, lower = NULL, upper = NULL, ...)
Arguments
v |
Source vector. If |
m |
Number of elements to choose. If |
... |
Further arguments passed to methods. |
repetition |
Logical value indicating whether combinations/permutations should be with or without repetition. The default is |
freqs |
A vector of frequencies used for producing all combinations/permutations of a multiset of |
lower |
The lower bound. Combinations/permutations are generated lexicographically, thus utilizing this argument will determine which specific combination/permutation to start generating from (e.g. |
upper |
The upper bound. Similar to If the output is constrained and In addition to the benefits listed for |
constraintFun |
Function to be applied to the elements of |
comparisonFun |
Comparison operator that will be used to compare When
In other words, the first comparison operator is applied to the first limit and the second operator is applied to the second limit. |
limitConstraints |
This is the value(s) that will be used for comparison. Can be passed as a single value or a vector of two numerical values. The default is |
keepResults |
A logical flag indicating if the result of E.g. The following are equivalent and will produce a
|
FUN |
Function to be applied to each combination/permutation. The default is |
Parallel |
Logical value indicating whether combinations/permutations should be generated in parallel using |
nThreads |
Specific number of threads to be used. The default is |
tolerance |
A numeric value greater than or equal to zero. This parameter is utilized when a constraint is applied on a numeric vector. The default value is 0 when it can be determined that whole values are being utilized, otherwise it is |
FUN.VALUE |
A template for the return value from |
Details
For the general case, finding all combinations/permutations with constraints is optimized by organizing them in such a way that when constraintFun
is applied, a partially monotonic sequence is produced. Combinations/permutations are added successively, until a particular combination exceeds the given constraint value for a given constraint/comparison function combo. After this point, we can safely skip several combinations knowing that they will exceed the given constraint value.
There are special cases where more efficient algorithms are dyncamically deployed. These cases center around the subject of integer partitions. See partitionsGeneral
for more information.
When there are any negative values in v
and constraintFun = "prod"
, producing a monotonic set is non-trivial for the general case. As a result, performance will suffer as all combinations/permutations must be tested against the constraint criteria.
Value
In general, a matrix with
m
orm + 1
columns, depending on the value ofkeepResults
If
FUN
is utilized andFUN.VALUE = NULL
, a list is returnedWhen both
FUN
andFUN.VALUE
are notNULL
, the return is modeled after the return ofvapply
. See the 'Value' section ofvapply
.
Note
-
Parallel
andnThreads
will be ignored in the following cases:When the output is constrained (except for most partitions cases)
If the class of the vector passed is
character
,raw
, andcomplex
(N.B.Rcpp::CharacterMatrix
is not thread safe). Alternatively, you can generate an indexing matrix in parallel.If
FUN
is utilized.
If either
constraintFun
,comparisonFun
orlimitConstraints
isNULL
–or– if the class of the vector passed islogical
,character
,raw
,factor
, orcomplex
, the constraint check will not be carried out. This is equivalent to simply finding all combinations/permutations ofv
choosem
.The maximum number of combinations/permutations that can be generated at one time is
2^{31} - 1
. Utilizinglower
andupper
makes it possible to generate additional combinations/permutations.Factor vectors are accepted. Class and level attributes are preserved except when
FUN
is used.Lexicographical ordering isn't guaranteed for permutations if
lower
isn't supplied and the output is constrained.If
lower
is supplied and the output is constrained, the combinations/permutations that will be tested will be in the lexicographical rangelower
toupper
or up to the total possible number of results ifupper
is not given. See the second paragraph for the definition ofupper
.-
FUN
will be ignored if the constraint check is satisfied.
Author(s)
Joseph Wood
References
Examples
comboGeneral(4, 3)
permuteGeneral(3)
permuteGeneral(factor(letters[1:3]), repetition = TRUE)
## permutations of the multiset :
## c(1,1,1,2,2,3)
permuteGeneral(table(c(1,1,1,2,2,3)))
## Example with list
comboGeneral(
v = list(
p1 = matrix(1:10, ncol = 2),
p2 = data.frame(a = letters, b = 1:26),
p3 = as.complex(1:10)
),
m = 2
)
#### Examples using "upper" and "lower":
## See specific range of permutations
permuteGeneral(75, 10, freqs = rep(1:3, 25),
lower = 1e12, upper = 1e12 + 10)
## Researcher only needs 10 7-tuples of mySamp
## such that the sum is greater than 7200.
## Generate some random data
set.seed(1009)
mySamp = rnorm(75, 997, 23)
comboGeneral(mySamp, 7, constraintFun = "sum",
comparisonFun = ">", limitConstraints = 7200, upper = 10)
## Similarly, you can use "lower" to obtain the last rows.
## Generate the last 10 rows
comboGeneral(mySamp, 7, lower = choose(75, 7) - 9)
## Or if you would like to generate a specific chunk,
## use both "lower" and "upper". E.g. Generate one
## million combinations starting with the 900,000,001
## lexicographic combination.
t1 = comboGeneral(mySamp, 7,
lower = 9*10^8 + 1,
upper = 9*10^8 + 10^6)
## class of the source vector is preserved
class(comboGeneral(5,3)[1,]) == class(1:5)
class(comboGeneral(c(1,2:5),3)[1,]) == class(c(1,2:5))
class(comboGeneral(factor(month.name),3)[1,]) == class(factor(month.name))
## Using keepResults will add a column of results
comboGeneral(-3, 6, TRUE,
constraintFun = "sum",
comparisonFun = "==",
limitConstraints = -8,
keepResults = TRUE)
## Using multiple constraints:
## Get combinations such that the product
## is between 3000 and 4000 inclusive
comboGeneral(5, 7, TRUE, constraintFun = "prod",
comparisonFun = c(">=","<="),
limitConstraints = c(3000, 4000),
keepResults = TRUE)
## Or, get the combinations such that the
## product is less than or equal to 10 or
## greater than or equal to 40000
comboGeneral(5, 7, TRUE, constraintFun = "prod",
comparisonFun = c("<=",">="),
limitConstraints = c(10, 40000),
keepResults = TRUE)
#### General subset sum problem
set.seed(516781810)
comboGeneral(runif(100, 0, 42), 5, constraintFun = "mean",
comparisonFun = "==", limitConstraints = 30,
tolerance = 0.0000002)
#### Integer Partitions
comboGeneral(0:5, 5, TRUE, constraintFun = "sum",
comparisonFun = "==", limitConstraints = 5)
## Using FUN
comboGeneral(10000, 5, lower = 20, upper = 22,
FUN = function(x) {
which(cummax(x) %% 2 == 1)
})
## Not run:
## Parallel example generating more than 2^31 - 1 combinations.
library(parallel)
numCores = detectCores() - 1
## 10086780 evenly divides choose(35, 15) and is "small enough" to
## generate quickly in chunks.
system.time(mclapply(seq(1, comboCount(35, 15), 10086780), function(x) {
a = comboGeneral(35, 15, lower = x, upper = x + 10086779)
## do something
x
}, mc.cores = numCores))
## Find 13-tuple combinations of 1:25 such
## that the mean is less than 10
system.time(myComb <- comboGeneral(25, 13, FALSE,
constraintFun = "mean",
comparisonFun = "<",
limitConstraints = 10))
## Alternatively, you must generate all combinations and subsequently
## subset to obtain the combinations that meet the criteria
system.time(myComb2 <- combn(25, 13))
system.time(myCols <- which(colMeans(myComb2) < 10))
system.time(myComb2 <- myComb2[, myCols])
## Any variation is much slower
system.time(myComb2 <- combn(25, 13)[,combn(25, 13, mean) < 10])
## Test equality with myComb above
all.equal(myComb, t(myComb2))
## Fun example... see stackoverflow:
## https://stackoverflow.com/q/22218640/4408538
system.time(permuteGeneral(seq(0L,100L,10L), 8, TRUE,
constraintFun = "sum",
comparisonFun = "==",
limitConstraints = 100))
## These are called weak integer compositions. Below, we call
## compositionsGeneral which gives the same output except it
## in lexicographical order. See 'Note' above
system.time(compositionsGeneral(seq(0L,100L,10L), 8, TRUE, weak = TRUE))
## End(Not run)