R: Permutaciones y combinaciones con / sin reemplazo y para elementos distintos / no distintivos / multiset

En este hilo, bash incluir aquí todas las preguntas frecuentes y sus respuestas. Espero que esto sea útil para alguien.

Pregunta general : ¿cómo generar secuencias de r objetos a partir de n objetos?

  • combinación vs permutación.
  • con reemplazo vs sin reemplazo.
  • elementos distintos frente a elementos no diferenciados (multisectos).

Hay en total 2^3=8 preguntas de este tipo.

[Actualizar]

Josh O’Brien sugiere que las 8 preguntas están relacionadas de manera multiplicativa . De hecho, las preguntas “distintas” se incluyen de manera doble, mientras que las preguntas “no distintas” no se incluyen. De todos modos, es interesante comparar las 8 preguntas aquí de manera multiplicativa. Ver los comentarios para más lecturas.

EDITAR : He actualizado la respuesta para utilizar un paquete de arrangements más eficientes

Primeros pasos para usar el arrangement

arreglos contiene algunos generadores e iteradores eficientes para permutaciones y combinaciones. Se ha demostrado que los arrangements superan a la mayoría de los paquetes existentes de tipo similar. Algunos puntos de referencia se pueden encontrar aquí .

Aquí están las respuestas a las preguntas anteriores

 # 1) combinations: without replacement: distinct items combinations(5, 2) [,1] [,2] [1,] 1 2 [2,] 1 3 [3,] 1 4 [4,] 1 5 [5,] 2 3 [6,] 2 4 [7,] 2 5 [8,] 3 4 [9,] 3 5 [10,] 4 5 # 2) combinations: with replacement: distinct items combinations(5, 2, replace=TRUE) [,1] [,2] [1,] 1 1 [2,] 1 2 [3,] 1 3 [4,] 1 4 [5,] 1 5 [6,] 2 2 [7,] 2 3 [8,] 2 4 [9,] 2 5 [10,] 3 3 [11,] 3 4 [12,] 3 5 [13,] 4 4 [14,] 4 5 [15,] 5 5 # 3) combinations: without replacement: non distinct items combinations(x = c("a", "b", "c"), freq = c(2, 1, 1), k = 2) [,1] [,2] [1,] "a" "a" [2,] "a" "b" [3,] "a" "c" [4,] "b" "c" # 4) combinations: with replacement: non distinct items combinations(x = c("a", "b", "c"), k = 2, replace = TRUE) # as `freq` does not matter [,1] [,2] [1,] "a" "a" [2,] "a" "b" [3,] "a" "c" [4,] "b" "b" [5,] "b" "c" [6,] "c" "c" # 5) permutations: without replacement: distinct items permutations(5, 2) [,1] [,2] [1,] 1 2 [2,] 1 3 [3,] 1 4 [4,] 1 5 [5,] 2 1 [6,] 2 3 [7,] 2 4 [8,] 2 5 [9,] 3 1 [10,] 3 2 [11,] 3 4 [12,] 3 5 [13,] 4 1 [14,] 4 2 [15,] 4 3 [16,] 4 5 [17,] 5 1 [18,] 5 2 [19,] 5 3 [20,] 5 4 # 6) permutations: with replacement: distinct items permutations(5, 2, replace = TRUE) [,1] [,2] [1,] 1 1 [2,] 1 2 [3,] 1 3 [4,] 1 4 [5,] 1 5 [6,] 2 1 [7,] 2 2 [8,] 2 3 [9,] 2 4 [10,] 2 5 [11,] 3 1 [12,] 3 2 [13,] 3 3 [14,] 3 4 [15,] 3 5 [16,] 4 1 [17,] 4 2 [18,] 4 3 [19,] 4 4 [20,] 4 5 [21,] 5 1 [22,] 5 2 [23,] 5 3 [24,] 5 4 [25,] 5 5 # 7) permutations: without replacement: non distinct items permutations(x = c("a", "b", "c"), freq = c(2, 1, 1), k = 2) [,1] [,2] [1,] "a" "a" [2,] "a" "b" [3,] "a" "c" [4,] "b" "a" [5,] "b" "c" [6,] "c" "a" [7,] "c" "b" # 8) permutations: with replacement: non distinct items permutations(x = c("a", "b", "c"), k = 2, replace = TRUE) # as `freq` doesn't matter [,1] [,2] [1,] "a" "a" [2,] "a" "b" [3,] "a" "c" [4,] "b" "a" [5,] "b" "b" [6,] "b" "c" [7,] "c" "a" [8,] "c" "b" [9,] "c" "c" 

Compare con otros paquetes

Hay algunas ventajas de usar arrangements sobre los paquetes existentes.

  1. Marco integral: no tiene que usar diferentes paquetes para diferentes métodos.

  2. Es muy eficiente Consulte https://randy3k.github.io/arrangements/articles/benchmark.html para ver algunos puntos de referencia.

  3. Es eficiente desde el punto de vista de la memoria, ¡es capaz de generar los 13! permutación de 1 a 13, los paquetes existentes no podrán hacerlo debido a la limitación del tamaño de la matriz. El método getnext() de los iteradores permite a los usuarios obtener los arreglos uno por uno.

  4. Los arreglos generados están en orden de diccionario que pueden ser deseados para algunos usuarios.

Una caminata por una rebanada de combinatoria en R *

A continuación, examinamos paquetes equipados con la capacidad de generar combinaciones y permutaciones. Si he omitido algún paquete, por favor, perdóneme y por favor deje un comentario o mejor aún, edite esta publicación.

Esquema de análisis:

  1. Introducción
  2. Combinaciones
  3. Permutaciones
  4. Multisectos
  5. Resumen
  6. Memoria

Antes de comenzar, notamos que las combinaciones / permutaciones con reemplazo de elementos distintos vs. no distintivos elegidos m a la vez son equivalentes. Esto es así, porque cuando tenemos reemplazo, no es específico. Por lo tanto, no importa cuántas veces se produzca originalmente un elemento en particular, la salida tendrá una instancia (s) de ese elemento repetido de 1 a m veces.

1. Introducción

  1. gtools v 3.8.1
  2. combinat v 0.0-8
  3. multicool v multicool
  4. partitions v 1.9-19
  5. RcppAlgos v 2.0.1 (soy el autor)
  6. arrangements v 1.1.0
  7. gRbase v gRbase

No permute , permutations ni gRbase::aperm/ar_perm ya que en realidad no están destinados a atacar estos tipos de problemas.

| ————————————— VISIÓN GENERAL ——— ——————————- |

 |_______________| gtools | combinat | multicool | partitions | | comb rep | Yes | | | | | comb NO rep | Yes | Yes | | | | perm rep | Yes | | | | | perm NO rep | Yes | Yes | Yes | Yes | | perm multiset | | | Yes | | | comb multiset | | | | | |accepts factors| | Yes | | | | m at a time | Yes | Yes/No | | | |general vector | Yes | Yes | Yes | | | iterable | | | Yes | | |parallelizable | | | | | | big integer | | | | | |_______________| iterpc | arrangements | RcppAlgos | gRbase | | comb rep | Yes | Yes | Yes | | | comb NO rep | Yes | Yes | Yes | Yes | | perm rep | Yes | Yes | Yes | | | perm NO rep | Yes | Yes | Yes | * | | perm multiset | Yes | Yes | Yes | | | comb multiset | Yes | Yes | Yes | | |accepts factors| | Yes | Yes | | | m at a time | Yes | Yes | Yes | Yes | |general vector | Yes | Yes | Yes | Yes | | iterable | | Yes | Partially | | |parallelizable | | Yes | Yes | | | big integer | | Yes | | | 

Las tareas, m at a time y general vector , se refieren a la capacidad de generar resultados ” m a la vez” (cuando m es menor que la longitud del vector) y reorganizar un “vector general” en oposición a 1:n . En la práctica, generalmente nos preocupamos por encontrar reordenamientos de un vector general, por lo tanto, todos los exámenes a continuación reflejarán esto (cuando sea posible).

Todos los puntos de referencia se ejecutaron en 3 configuraciones diferentes.

  1. Macbook Pro i7 16Gb
  2. Macbook Air i5 4Gb
  3. Lenovo con Windows 7 i5 8Gb

Los resultados listados se obtuvieron de la configuración n. ° 1 (es decir, MBPro). Los resultados para los otros dos sistemas fueron similares. Además, gc() se llama periódicamente para garantizar que toda la memoria esté disponible (Consulte ?gc ).

2. Combinaciones

Primero, examinamos las combinaciones sin reemplazo elegido de a la vez.

  1. RcppAlgos
  2. combinat (o utils )
  3. gtools
  4. arrangements
  5. gRbase

Cómo:

 library(RcppAlgos) library(arrangements) library(microbenchmark) options(digits = 4) set.seed(13) testVector1 < - sort(sample(100, 17)) m <- 9 t1 <- comboGeneral(testVector1, m) ## returns matrix with m columns t3 <- combinat::combn(testVector1, m) ## returns matrix with m rows t4 <- gtools::combinations(17, m, testVector1) ## returns matrix with m columns identical(t(t3), t4) ## must transpose to compare #> [1] TRUE t5 < - combinations(testVector1, m) identical(t1, t5) #> [1] TRUE t6 < - gRbase::combnPrim(testVector1, m) identical(t(t6)[do.call(order, as.data.frame(t(t6))),], t1) #> [1] TRUE 

Punto de referencia:

 microbenchmark(cbRcppAlgos = comboGeneral(testVector1, m), cbGRbase = gRbase::combnPrim(testVector1, m), cbGtools = gtools::combinations(17, m, testVector1), cbCombinat = combinat::combn(testVector1, m), cbArrangements = combinations(17, m, testVector1), unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgos 1.064 1.079 1.160 1.012 1.086 2.318 100 #> cbGRbase 7.335 7.509 5.728 6.807 5.390 1.608 100 #> cbGtools 426.536 408.807 240.101 310.848 187.034 63.663 100 #> cbCombinat 97.756 97.586 60.406 75.415 46.391 41.089 100 #> cbArrangements 1.000 1.000 1.000 1.000 1.000 1.000 100 

Ahora, examinamos combinaciones con reemplazo elegido m a la vez.

  1. RcppAlgos
  2. gtools
  3. arrangements

Cómo:

 library(RcppAlgos) library(arrangements) library(microbenchmark) options(digits = 4) set.seed(97) testVector2 < - sort(rnorm(10)) m <- 8 t1 <- comboGeneral(testVector2, m, repetition = TRUE) t3 <- gtools::combinations(10, m, testVector2, repeats.allowed = TRUE) identical(t1, t3) #> [1] TRUE ## arrangements t4 < - combinations(testVector2, m, replace = TRUE) identical(t1, t4) #> [1] TRUE 

Punto de referencia:

 microbenchmark(cbRcppAlgos = comboGeneral(testVector2, m, TRUE), cbGtools = gtools::combinations(10, m, testVector2, repeats.allowed = TRUE), cbArrangements = combinations(testVector2, m, replace = TRUE), unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgos 1.000 1.000 1.000 1.000 1.000 1.00000 100 #> cbGtools 384.990 269.683 80.027 112.170 102.432 3.67517 100 #> cbArrangements 1.057 1.116 0.618 1.052 1.002 0.03638 100 

3. Permutaciones

Primero, examinamos las permutaciones sin reemplazo elegidas de a la vez.

  1. RcppAlgos
  2. gtools
  3. arrangements

Cómo:

 library(RcppAlgos) library(arrangements) library(microbenchmark) options(digits = 4) set.seed(101) testVector3 < - as.integer(c(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)) ## RcppAlgos... permuteGeneral same as comboGeneral above t1 <- permuteGeneral(testVector3, 6) ## gtools... permutations same as combinations above t3 <- gtools::permutations(10, 6, testVector3) identical(t1, t3) #> [1] TRUE ## arrangements t4 < - permutations(testVector3, 6) identical(t1, t4) #> [1] TRUE 

Punto de referencia:

 microbenchmark(cbRcppAlgos = permuteGeneral(testVector3, 6), cbGtools = gtools::permutations(10, 6, testVector3), cbArrangements = permutations(testVector3, 6), unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgos 1.079 1.027 1.106 1.037 1.003 5.37 100 #> cbGtools 158.720 92.261 85.160 91.856 80.872 45.39 100 #> cbArrangements 1.000 1.000 1.000 1.000 1.000 1.00 100 

A continuación, examinamos permutaciones sin reemplazo con un vector general (devolviendo todas las permutaciones).

  1. RcppAlgos
  2. gtools
  3. combinat
  4. multicool
  5. arrangements

Cómo:

 library(RcppAlgos) library(arrangements) library(microbenchmark) options(digits = 4) set.seed(89) testVector3 < - as.integer(c(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)) testVector3Prime <- testVector3[1:7] ## For RcppAlgos, & gtools (see above) ## combinat t4 <- combinat::permn(testVector3Prime) ## returns a list of vectors ## convert to a matrix t4 <- do.call(rbind, t4) ## multicool.. we must first call initMC t5 <- multicool::allPerm(multicool::initMC(testVector3Prime)) ## returns a matrix with n columns all.equal(t4[do.call(order,as.data.frame(t4)),], t5[do.call(order,as.data.frame(t5)),]) #> [1] TRUE 

Punto de referencia:

 microbenchmark(cbRcppAlgos = permuteGeneral(testVector3Prime, 7), cbGtools = gtools::permutations(7, 7, testVector3Prime), cbCombinat = combinat::permn(testVector3Prime), cbMulticool = multicool::allPerm(multicool::initMC(testVector3Prime)), cbArrangements = permutations(x = testVector3Prime, k = 7), unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgos 1.152 1.275 0.7508 1.348 1.342 0.3159 100 #> cbGtools 965.465 817.645 340.4159 818.137 661.068 12.7042 100 #> cbCombinat 280.207 236.853 104.4777 238.228 208.467 9.6550 100 #> cbMulticool 2573.001 2109.246 851.3575 2039.531 1638.500 28.3597 100 #> cbArrangements 1.000 1.000 1.0000 1.000 1.000 1.0000 100 

Ahora, examinamos las permutaciones sin reemplazo para 1:n (devolviendo todas las permutaciones).

  1. RcppAlgos
  2. gtools
  3. combinat
  4. multicool
  5. partitions
  6. arrangements

Cómo:

 library(RcppAlgos) library(arrangements) library(microbenchmark) options(digits = 4) set.seed(89) t1 < - partitions::perms(7) ## returns an object of type 'partition' with n rows identical(t(as.matrix(t1)), permutations(7,7)) #> [1] TRUE 

Punto de referencia:

 microbenchmark(cbRcppAlgos = permuteGeneral(7, 7), cbGtools = gtools::permutations(7, 7), cbCombinat = combinat::permn(7), cbMulticool = multicool::allPerm(multicool::initMC(1:7)), cbPartitions = partitions::perms(7), cbArrangements = permutations(7, 7), unit = "relative") #> Unit: relative #> expr min lq mean median uq max #> cbRcppAlgos 1.235 1.429 1.412 1.503 1.484 1.720 #> cbGtools 1152.826 1000.736 812.620 939.565 793.373 499.029 #> cbCombinat 347.446 304.866 260.294 296.521 248.343 284.001 #> cbMulticool 3001.517 2416.716 1903.903 2237.362 1811.006 1311.219 #> cbPartitions 2.469 2.536 2.801 2.692 2.999 2.472 #> cbArrangements 1.000 1.000 1.000 1.000 1.000 1.000 #> neval #> 100 #> 100 #> 100 #> 100 #> 100 #> 100 

Por último, examinamos permutaciones con reemplazo.

  1. RcppAlgos
  2. iterpc
  3. gtools
  4. arrangements

Cómo:

 library(RcppAlgos) library(arrangements) library(microbenchmark) options(digits = 4) set.seed(34) testVector3 < - as.integer(c(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)) t1 <- permuteGeneral(testVector3, 5, repetition = TRUE) t3 <- gtools::permutations(10, 5, testVector3, repeats.allowed = TRUE) t4 <- permutations(x = testVector3, k = 5, replace = TRUE) 

Este próximo punto de referencia es un poco sorprendente dados los resultados hasta ahora.

 microbenchmark(cbRcppAlgos = permuteGeneral(testVector3, 5, TRUE), cbGtools = gtools::permutations(10, 5, testVector3, repeats.allowed = TRUE), cbArrangements = permutations(x = testVector3, k = 5, replace = TRUE), unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgos 1.106 0.9183 1.200 1.030 1.063 1.701 100 #> cbGtools 2.426 2.1815 2.068 1.996 2.127 1.367 100 #> cbArrangements 1.000 1.0000 1.000 1.000 1.000 1.000 100 

Eso no es un error tipográfico ... gtools::permutations es casi tan rápido como las otras funciones comstackdas. Animo al lector a consultar el código fuente de gtools::permutations ya que es una de las pantallas más elegantes de progtwigción ( R o no).

4. Multiedades

Primero, examinamos las combinaciones de multisedes.

  1. RcppAlgos
  2. arrangements

Para encontrar combinaciones / permutaciones de RcppAlgos , con RcppAlgos use los argumentos de freqs para especificar cuántas veces se repite cada elemento del vector fuente, v .

 library(RcppAlgos) library(arrangements) library(microbenchmark) options(digits = 4) set.seed(496) myFreqs < - sample(1:5, 10, replace = TRUE) ## This is how many times each element will be repeated myFreqs #> [1] 2 4 4 5 3 2 2 2 3 4 testVector4 < - as.integer(c(1, 2, 3, 5, 8, 13, 21, 34, 55, 89)) t1 <- comboGeneral(testVector4, 12, freqs = myFreqs) t3 <- combinations(freq = myFreqs, k = 12, x = testVector4) identical(t1, t3) #> [1] TRUE 

Punto de referencia:

 microbenchmark(cbRcppAlgos = comboGeneral(testVector4, 12, freqs = myFreqs), cbArrangements = combinations(freq = myFreqs, k = 12, x = testVector4), unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgos 1.000 1.000 1.000 1.000 1.000 1.000 100 #> cbArrangements 1.254 1.221 1.287 1.259 1.413 1.173 100 

Para las permutaciones de multisecuencias elegidas de forma simultánea, tenemos:

  1. RcppAlgos
  2. arrangements

Cómo:

 library(RcppAlgos) library(arrangements) library(microbenchmark) options(digits = 4) set.seed(8128) myFreqs < - sample(1:3, 5, replace = TRUE) testVector5 <- sort(runif(5)) myFreqs #> [1] 2 2 2 1 3 t1 < - permuteGeneral(testVector5, 7, freqs = myFreqs) t3 <- permutations(freq = myFreqs, k = 7, x = testVector5) identical(t1, t3) #> [1] TRUE 

Punto de referencia:

 microbenchmark(cbRcppAlgos = permuteGeneral(testVector5, 7, freqs = myFreqs), cbArrangements = permutations(freq = myFreqs, k = 7, x = testVector5), unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgos 1.461 1.327 1.282 1.177 1.176 1.101 100 #> cbArrangements 1.000 1.000 1.000 1.000 1.000 1.000 100 

Para las permutaciones de multisectos que devuelven todas las permutaciones, tenemos:

  1. RcppAlgos
  2. multicool
  3. arrangements

Cómo:

 library(RcppAlgos) library(arrangements) library(microbenchmark) options(digits = 4) set.seed(8128) myFreqs2 < - c(2,1,2,1,2) testVector6 <- (1:5)^3 ## For multicool, you must have the elements explicitly repeated testVector6Prime <- rep(testVector6, times = myFreqs2) t3 <- multicool::allPerm(multicool::initMC(testVector6Prime)) ## for comparison t1 <- permuteGeneral(testVector6, freqs = myFreqs2) identical(t1[do.call(order,as.data.frame(t1)),], t3[do.call(order,as.data.frame(t3)),]) #> [1] TRUE 

Punto de referencia:

 microbenchmark(cbRcppAlgos = permuteGeneral(testVector6, freqs = myFreqs2), cbMulticool = multicool::allPerm(multicool::initMC(testVector6Prime)), cbArrangements = permutations(freq = myFreqs2, x = testVector6), unit = "relative") #> Unit: relative #> expr min lq mean median uq max neval #> cbRcppAlgos 1.276 1.374 1.119 1.461 1.39 0.8856 100 #> cbMulticool 2434.652 2135.862 855.946 2026.256 1521.74 31.0651 100 #> cbArrangements 1.000 1.000 1.000 1.000 1.00 1.0000 100 

5. Resumen

Ambos gtools y combinat son paquetes bien establecidos para reorganizar elementos de un vector. Con gtools hay algunas opciones más (ver la descripción anterior) y con combinat , puede reorganizar los factors . Con multicool , uno puede reorganizar multisedes. Aunque las partitions y gRbase son limitadas para los fines de esta pregunta, son potencias repletas de funciones altamente eficientes para tratar con particiones y objetos de matriz, respectivamente.

arrangements

  1. La salida está en orden de diccionario.
  2. Permite al usuario especificar el formato a través del argumento de layout ( r = row-major , c = column-major , y l = list ).
  3. Ofrece métodos convenientes como collect & getnext cuando se trabaja con iteradores.
  4. Permite la generación de más de 2^31 - 1 combinaciones / permutaciones a través de getnext . NB RcppAlgos (a través de la parte lower/upper ver a continuación) y multicool (a través de nextPerm ) también son capaces de hacer esto.
  5. Hablando de getnext , esta función permite un número específico de resultados al utilizar el argumento d .
  6. Admite los enteros grandes de gmp para calcular el número de combinaciones / permutaciones.

Observar:

 library(arrangements) icomb < - icombinations(1000, 7) icomb$getnext(d = 5) #> [,1] [,2] [,3] [,4] [,5] [,6] [,7] #> [1,] 1 2 3 4 5 6 7 #> [2,] 1 2 3 4 5 6 8 #> [3,] 1 2 3 4 5 6 9 #> [4,] 1 2 3 4 5 6 10 #> [5,] 1 2 3 4 5 6 11 

Esta característica es realmente agradable cuando solo quieres algunas combinaciones / permutaciones. Con los métodos tradicionales, tendrías que generar todas las combinaciones / permutaciones y luego un subconjunto. Esto haría imposible el ejemplo anterior ya que hay más de 10^17 resultados (es decir, ncombinations(1000, 7, bigz = TRUE) = 194280608456793000).

Esta característica junto con las mejoras a los generadores en los arrangements , le permiten ser muy eficiente con respecto a la memoria.

RcppAlgos

  1. La salida está en orden de diccionario.
  2. Hay funciones de restricción convenientes que no discutiremos aquí ya que están fuera del tema de esta pregunta. Solo señalaré que los tipos de problemas que se pueden resolver mediante la utilización de estas características fueron la motivación para crear este paquete.
  3. Hay un argumento upper (formalmente rowCap ) que es análogo al argumento d de getnext .

Observar:

 library(RcppAlgos) comboGeneral(1000, 7, upper = 5) #> [,1] [,2] [,3] [,4] [,5] [,6] [,7] #> [1,] 1 2 3 4 5 6 7 #> [2,] 1 2 3 4 5 6 8 #> [3,] 1 2 3 4 5 6 9 #> [4,] 1 2 3 4 5 6 10 #> [5,] 1 2 3 4 5 6 11 
  1. Además, a partir de 2.0.0 , hay un argumento llamado lower que permite iniciar la generación en una combinación / permutación específica. Esto se configura muy bien para la paralelización y permite una generación rápida más allá de 2^31 - 1 ya que los fragmentos se generan de forma independiente.

Ejemplo paralelo con más de 6 mil millones de combinaciones:

 system.time(parallel::mclapply(seq(1,6397478649,4390857), function(x) { a < - comboGeneral(25, 15, freqs = c(rep(1:5, 5)), lower = x, upper = x + 4390856) ## do something x }, mc.cores = 7)) #> user system elapsed #> 510.623 140.970 109.496 

En caso de que se esté preguntando cómo se escalará cada paquete, lo dejaré con este ejemplo final que mide qué tan rápido cada paquete puede generar más de 100 millones de resultados (NB gtools::combinations se deja aquí ya que arrojará el error: evaluation nested too deeply... ). Además, estamos llamando explícitamente a combn del paquete utils porque no pude obtener una ejecución exitosa de combinat::combn . Las diferencias en el uso de la memoria entre estos dos es bastante extraño dado que son solo marginalmente diferentes (ver ?utils::combn en la sección "Autores").

Observar:

 library(RcppAlgos) library(arrangements) library(microbenchmark) options(digits = 4) set.seed(2187) testVector7 < - sort(sample(10^7, 10^3)) system.time(utils::combn(testVector7, 3)) #> user system elapsed #> 179.956 5.687 187.159 system.time(RcppAlgos::comboGeneral(testVector7, 3)) #> user system elapsed #> 1.136 0.758 1.937 system.time(arrangements::combinations(x = testVector7, k = 3)) #> user system elapsed #> 1.963 0.930 2.910 system.time(RcppAlgos::permuteGeneral(testVector7[1:500], 3)) #> user system elapsed #> 1.095 0.631 1.738 system.time(arrangements::permutations(x = testVector7[1:500], k = 3)) #> user system elapsed #> 1.399 0.584 1.993 

6. Memoria

Al ejecutar las comboGeneral y arrangements::combinations , la memoria saltará casi 2 Gbs antes de llamar a gc . Esto parece correcto ya que #rows * #nols * bytesPerCell / 2^30 bytes = choose(1000,3) * 3 * 4 / 2^30 bytes = (166167000 * 3 * 4)/2^30 = 1.857 Gbs ). Sin embargo, al ejecutar combn , el comportamiento de la memoria era erático (por ejemplo, a veces usaría todos los 16 Gb de memoria y otras veces solo boostía un par de Gbs). Cuando probé esto en la configuración de Windows, a menudo se bloqueaba.

Podemos confirmar esto usando Rprof junto con summaryRporf . Observar:

 Rprof("RcppAlgos.out", memory.profiling = TRUE) t1 < - RcppAlgos::comboGeneral(testVector7, 3) Rprof(NULL) summaryRprof("RcppAlgos.out", memory = "both")$by.total total.time total.pct mem.total self.time self.pct "CombinatoricsRcpp" 1.2 100 1901.6 1.2 100 "RcppAlgos::comboGeneral" 1.2 100 1901.6 0.0 0 Rprof("arrangements.out", memory.profiling = TRUE) t3 <- arrangements::combinations(10^3, 3, testVector7) Rprof(NULL) summaryRprof("arrangements.out", memory = "both")$by.total total.time total.pct mem.total self.time self.pct ".Call" 2.08 99.05 1901.6 2.08 99.05 

Con RcppAlgos y arrangements , mem.total registra algo más de 1900 Mb .

Y aquí está el perfil de memoria en un vector más pequeño que compara gtools , utils y combinat .

 testVector7Prime < - testVector7[1:300] Rprof("combinat.out", memory.profiling = TRUE) t3 <- combinat::combn(testVector7Prime, 3) Rprof(NULL) summaryRprof("combinat.out", memory = "both")$by.total total.time total.pct mem.total self.time self.pct "combinat::combn" 3.98 100.00 1226.9 3.72 93.47 Rprof("utils.out", memory.profiling = TRUE) t4 <- utils::combn(testVector7Prime, 3) Rprof(NULL) summaryRprof("utils.out", memory = "both")$by.total total.time total.pct mem.total self.time self.pct "utils::combn" 2.52 100.00 1952.7 2.50 99.21 Rprof("gtools.out", memory.profiling = TRUE) t5 <- gtools::combinations(300, 3, testVector7Prime) Rprof(NULL) summaryRprof("gtools.out", memory = "both")$by.total total.time total.pct mem.total self.time self.pct "rbind" 4.94 95.00 6741.6 4.40 84.62 

Curiosamente, utils::combn y combinat::combn usan diferentes cantidades de memoria y toman diferentes cantidades de tiempo para ejecutarse. Esto no se sostiene con vectores más pequeños:

 microbenchmark(combinat::combn(2:13, 6), utils::combn(2:13, 6)) Unit: microseconds expr min lq mean median uq max neval combinat::combn(2:13, 6) 527.378 567.946 629.1268 577.163 604.3270 1816.744 100 utils::combn(2:13, 6) 663.150 712.872 750.8008 725.716 771.1345 1205.697 100 

Y con gtools la memoria total utilizada es un poco más de 3 veces mayor que utils . Cabe señalar que para estos 3 paquetes, obtuve resultados diferentes cada vez que los ejecuté (por ejemplo, para combinat::combn veces obtenía 9000 Mb y luego obtenía 13000 Mb).

Aún así, ninguno puede coincidir RcppAlgos arrangements OR de RcppAlgos . Ambos solo usan 51 Mb cuando se ejecutan en el ejemplo anterior.

secuencia de comandos de referencia: https://gist.github.com/randy3k/bd5730a6d70101c7471f4ae6f453862e (representado por https://github.com/tidyverse/reprex )

*: Un homenaje a A Walk an Combinatorics de Miklós Bóna