Queremos brindarte la mejor respuesta que hallamos on line. Nosotros queremos que te sirva de ayuda y si quieres aportar alguna mejora hazlo libremente.
Solución:
Esto es precisamente lo que combo/permuteGeneral de RcppAlgos (Soy el autor) fueron creados. Dado que tenemos repetición de elementos específicos en nuestro vector de muestra, encontraremos combinaciones de conjuntos múltiples que cumplan con nuestros criterios. Tenga en cuenta que esto es diferente al caso más común de generar combinaciones con repetición donde se permite que cada elemento se repita metro veces. Para muchas funciones de generación de combinación, los conjuntos múltiples plantean problemas a medida que se introducen duplicados y deben tratarse. Esto puede convertirse en un cuello de botella en su código si el tamaño de sus datos es bastante grande. Las funciones en RcppAlgos maneje estos casos de manera eficiente sin crear resultados duplicados. Debo mencionar que hay un par de otras geniales bibliotecas que manejan multisets bastante bien: multicool y arrangements.
Pasando a la tarea en cuestión, podemos utilizar los argumentos de restricción de comboGeneral para encontrar todas las combinaciones de nuestro vector que cumplan con un criterio específico:
vec <- c(1,1,2,3,5) ## using variables from @r2evans
uni <- unique(vec)
myRep <- rle(vec)$lengths
ans <- 5
library(RcppAlgos)
lapply(seq_along(uni), function(x)
comboGeneral(uni, x, freqs = myRep,
constraintFun = "sum",
comparisonFun = "==",
limitConstraints = ans)
)
[[1]]
[,1]
[1,] 5
[[2]]
[,1] [,2]
[1,] 2 3
[[3]]
[,1] [,2] [,3]
[1,] 1 1 3
[[4]]
[,1] [,2] [,3] [,4] ## no solutions of length 4
Estas funciones están altamente optimizadas y se extienden bien a casos más grandes. Por ejemplo, considere el siguiente ejemplo que produciría más de 30 millones de combinaciones:
## N.B. Using R 4.0.0 with new updated RNG introduced in 3.6.0
set.seed(42)
bigVec <- sort(sample(1:30, 40, TRUE))
rle(bigVec)
Run Length Encoding
lengths: int [1:22] 2 1 2 3 4 1 1 1 2 1 ...
values : int [1:22] 1 2 3 4 5 7 8 9 10 11 ...
bigUni <- unique(bigVec)
bigRep <- rle(bigVec)$lengths
bigAns <- 199
len <- 12
comboCount(bigUni, len, freqs = bigRep)
[1] 32248100
Todos los 300000+ resultados se devuelven muy rápidamente:
system.time(bigTest <- comboGeneral(bigUni, len, freqs = bigRep,
constraintFun = "sum",
comparisonFun = "==",
limitConstraints = bigAns))
user system elapsed
0.273 0.004 0.271
head(bigTest)
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12]
[1,] 1 1 2 3 4 25 26 26 26 27 28 30
[2,] 1 1 2 3 5 24 26 26 26 27 28 30
[3,] 1 1 2 3 5 25 25 26 26 27 28 30
[4,] 1 1 2 3 7 24 24 26 26 27 28 30
[5,] 1 1 2 3 7 24 25 25 26 27 28 30
[6,] 1 1 2 3 7 24 25 26 26 26 28 30
nrow(bigTest)
[1] 280018
all(rowSums(bigTest) == bigAns)
[1] TRUE
Apéndice
Debo mencionar que generalmente cuando veo un problema como: "encontrar todas las combinaciones que sumen un número en particular" mi primer pensamiento son las particiones enteras. Por ejemplo, en el problema relacionado Obteniendo todas las combinaciones que sumen 100 en R, podemos resolverlo fácilmente con el partitions Biblioteca. Sin embargo, este enfoque no se extiende al caso general (como tenemos aquí) donde el vector contiene una repetición específica o tenemos un vector que contiene valores que no se convierten fácilmente en un equivalente entero (por ejemplo, el vector (0.1, 0.2, 0.3, 0.4) se puede tratar fácilmente como 1:4, sin embargo tratando c(3.98486 7.84692 0.0038937 7.4879) como enteros y, posteriormente, aplicar un enfoque de particiones enteras requeriría una cantidad extravagante de potencia de cálculo que haría que este método fuera inútil).
Tomé tu combn idea y recorrió los posibles tamaños de los conjuntos.
func = function(x, total)
M = length(x)
y = NULL
total = 15
for (m in 1:M)
tmp = combn(x, m)
ind = which(colSums(tmp) == total)
if (length(ind) > 0)
for (j in 1:length(ind))
y = c(y, list(tmp[,ind[j]]))
return (unique(lapply(y, sort)))
x = c(1,1,2,3,5,8,13)
> func(x, 15)
[[1]]
[1] 2 13
[[2]]
[1] 1 1 13
[[3]]
[1] 2 5 8
[[4]]
[1] 1 1 5 8
[[5]]
[1] 1 1 2 3 8
Obviamente, esto tendrá problemas ya que M crece desde tmp crecerá bastante rápido y la longitud de y no puede ser (¿tal vez?) predeterminado.
Similar a la respuesta de Mickey, podemos usar combn dentro de otro mecanismo de bucle. Yo usaré lapply:
vec <- c(1,1,2,3,5)
ans <- 5
Filter(length, lapply(seq_len(length(vec)),
function(i)
v <- combn(vec, i)
v[, colSums(v) == ans, drop = FALSE]
))
# [[1]]
# [,1]
# [1,] 5
# [[2]]
# [,1]
# [1,] 2
# [2,] 3
# [[3]]
# [,1]
# [1,] 1
# [2,] 1
# [3,] 3
Puede omitir el Filter(length, parte, aunque puede devolver una serie de matrices vacías. Son bastante fáciles de manejar e ignorar, solo pensé que eliminarlos sería estéticamente preferido.
Este método le da una matriz con múltiples candidatos en cada columna, por lo que
ans <- 4
Filter(length, lapply(seq_len(length(vec)),
function(i)
v <- combn(vec, i)
v[, colSums(v) == ans, drop = FALSE]
))
# [[1]]
# [,1] [,2]
# [1,] 1 1
# [2,] 3 3
# [[2]]
# [,1]
# [1,] 1
# [2,] 1
# [3,] 2
Si los duplicados son un problema, siempre puede hacer:
Filter(length, lapply(seq_len(length(vec)),
function(i)
v <- combn(vec, i)
v <- v[, colSums(v) == ans, drop = FALSE]
v[,!duplicated(t(v)),drop = FALSE]
))
# [[1]]
# [,1]
# [1,] 1
# [2,] 3
# [[2]]
# [,1]
# [1,] 1
# [2,] 1
# [3,] 2
Comentarios y valoraciones de la guía
Si estás de acuerdo, eres capaz de dejar una reseña acerca de qué te ha gustado de este ensayo.