Saltar al contenido

¿Cómo generar permutaciones o combinaciones de objeto en R?

Por fin luego de tanto batallar hemos hallado el arreglo de esta traba que tantos lectores de nuestro espacio han presentado. Si tienes algo que aportar no dejes de aportar tu conocimiento.

Solución:

Un recorrido por una parte de la combinatoria en R *

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

Esquema del análisis:

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

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

1. Introducción

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

Yo no incluyo permute, permutations, o gRbase::aperm/ar_perm ya que en realidad no están destinados a atacar este tipo de problemas.

| ————————————— VISIÓN DE CONJUNTO —————————————- |

|_______________| 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, consulte la capacidad de generar resultados “metro en un momento cuando metro es menor que la longitud del vector) y reorganizar un “vector general” en lugar de 1:n. En la práctica, generalmente nos preocupa 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 de 16 Gb
  2. Macbook Air i5 4Gb
  3. Lenovo con Windows 7 i5 8Gb

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

2. Combinaciones

Primero, examinamos combinaciones sin reemplazo elegido metro 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 las combinaciones con el reemplazo elegido. metro 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 permutaciones sin reemplazo elegido metro 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 las 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 permutaciones sin reemplazo de 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 las 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 compiladas. Animo al lector a que consulte el código fuente de gtools::permutations ya que es una de las pantallas de programación más elegantes que existen (R o de otro modo).

4. Conjuntos múltiples

Primero, examinamos combinaciones de conjuntos múltiples.

  1. RcppAlgos
  2. arrangements

Para encontrar combinaciones / permutaciones de conjuntos múltiples, con RcppAlgos utilizar el freqs argumentos para especificar cuántas veces cada elemento del vector fuente, v, se repite.

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 permutaciones de conjuntos múltiples elegidos metro a la vez, 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 conjuntos múltiples 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 (consulte la descripción general anterior) y con combinat, puedes reorganizar factors. Con multicool, se puede reorganizar conjuntos múltiples. A pesar de que partitions y gRbase son limitadas para los propósitos de esta pregunta, son centrales eléctricas 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 layout argumento (r = row-major, c = column-major, y l = list).
  3. Ofrece métodos convenientes como collect Y 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. nótese bien RcppAlgos (vía lower/upper ver más abajo) y multicool (vía nextPerm) también son capaces de hacer esto.
  5. Hablando de getnext, esta función, permite un número específico de resultados utilizando el d argumento.
  6. Admite los números 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 buena cuando solo desea algunas combinaciones / permutaciones. Con los métodos tradicionales, tendría que generar todas las combinaciones / permutaciones y luego crear 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 arrangements, permiten que sea muy eficiente con respecto a la memoria.

RcppAlgos

  1. La salida está en orden de diccionario.
  2. Hay características 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 utilizando estas características fueron la motivación para crear este paquete.
  3. Hay un argumento upper (formalmente rowCap) que es análogo al d argumento 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 le permite a uno comenzar 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á 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 escala cada paquete, le dejo 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 combn desde el utils paquete porque no pude ejecutar correctamente combinat::combn. Las diferencias en el uso de la memoria entre estos dos son bastante extrañas 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 comboGeneral al igual que arrangements::combinations, la memoria saltará casi 2 Gbs antes de llamar gc. Esto parece correcto como #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 errático (por ejemplo, a veces usaba los 16 Gb de memoria y otras veces solo aumentaba un par de Gb). Cuando probé esto en la configuración de Windows, a menudo fallaba.

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 se registra un poco más 1900 Mb.

Y aquí está el perfil de memoria en un vector más pequeño comparando 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 requieren 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 la utils. Cabe señalar que para estos 3 paquetes, obtuve resultados diferentes cada vez que los ejecuté (por ejemplo, para combinat::combn a veces obtenía 9000 Mb y luego 13000 Mb).

Aún así, ninguno puede igualar RcppAlgosOarrangements. 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 Un paseo por la combinatoria de Miklós Bóna

EDITAR: He actualizado la respuesta para usar un paquete más eficiente. arrangements

Empezando a usar arrangement

arreglos contiene algunos generadores e iteradores eficientes para permutaciones y combinaciones. Se ha demostrado que arrangements supera 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"

Comparar con otros paquetes

Hay pocas ventajas de usar arrangements sobre los paquetes existentes.

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

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

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

  4. Los arreglos generados están en el orden del diccionario, lo que puede ser deseable para algunos usuarios.

Valoraciones y comentarios

Si piensas que ha resultado útil nuestro artículo, sería de mucha ayuda si lo compartieras con el resto programadores de esta manera contrubuyes a difundir nuestra información.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)

Tags : / / /

Utiliza Nuestro Buscador

Preguntas Relacionadas:

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *