repeticion reemplazo permutaciones orden muestras estadistica conteo con combinaciones combinacion r combinations permutation multiset r-faq

permutaciones - muestras sin orden y con reemplazo



R: Permutaciones y combinaciones con/sin reemplazo y para elementos distintos/no distintos/multiset (2)

Un paseo a través de una rebanada de combinatoria en R *

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

Esquema de análisis:

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

Antes de comenzar, notamos que las combinaciones / permutaciones con el 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 (s) instancia (s) de ese elemento repetidas de 1 am .

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 , o gRbase::aperm/ar_perm ya que no están realmente destinados a atacar este tipo de problemas.

| --------------------------------------- DESCRIPCIÓ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 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 16Gb
  2. Macbook Air i5 4Gb
  3. Lenovo ejecuta Windows 7 i5 8Gb

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

2. Combinaciones

Primero, examinamos las combinaciones sin reemplazo elegidas m 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 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 permutaciones sin reemplazo elegidas m 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 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

Ese no es un error tipográfico ... gtools::permutations es casi tan rápido como las otras funciones compiladas. Recomiendo al lector que revise el código fuente de gtools::permutations ya que es una de las pantallas más elegantes de programación ( R o de otro tipo).

4. Multisets

Primero, examinamos combinaciones de multisets.

  1. RcppAlgos
  2. arrangements

Para encontrar combinaciones / permutaciones de conjuntos RcppAlgos , con RcppAlgos use los argumentos 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 permutaciones de multisets elegidos m 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 permutaciones de multisets 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

Tanto gtools como combinat son paquetes bien establecidos para reorganizar elementos de un vector. Con gtools hay algunas opciones más (consulte la descripción general más arriba) y con combinat , puede reorganizar los factors . Con multicool , uno es capaz de reorganizar multisets. Si bien las partitions y gRbase están limitadas para los propósitos 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 mediante el argumento de layout ( r = row-major , c = column-major y l = list ).
  3. Ofrece métodos convenientes, como collect y 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 lower/upper ver más abajo) 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 utilizando 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 desea algunas combinaciones / permutaciones. Con los métodos tradicionales, tendría 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 de los generadores en los arrangements , le permite ser 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 de tema para 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 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 la 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 escala cada paquete, lo dejaré con este último ejemplo que mide la rapidez con que cada paquete puede generar más de 100 millones de resultados (NB gtools::combinations se gtools::combinations aquí ya que arrojará el error: la evaluation nested too deeply... ). Además, estamos llamando explícitamente a combn desde el paquete utils porque no pude obtener una ejecución exitosa de combinat::combn . Las diferencias en el uso de la memoria entre estos dos son bastante extrañas dado que solo son ligeramente diferentes (consulte ?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 y también a las arrangements::combinations , la memoria saltará casi 2 Gbs antes de llamar a 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 eratico (por ejemplo, a veces usaba todos los 16 Gb de memoria y otras solo aumentaba un par de Gbs). Cuando probé esto en la configuración de Windows, a menudo fallaba.

Podemos confirmar esto utilizando 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 & arrangements , mem.total registra poco 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 más que utils . Cabe señalar que para estos 3 paquetes, obtuve diferentes resultados cada vez que los ejecuté (por ejemplo, para combinat::combn veces obtendría 9000 Mb y luego obtendría 13000 Mb).

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

script 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

En este hilo, estoy tratando de incluir todas las preguntas frecuentes y sus respuestas aquí. Espero que esto sea de utilidad para alguien.

Pregunta general : ¿Cómo generar secuencias de r objetos desde n objetos?

  • combinación vs permutación.
  • Con reemplazo vs sin reemplazo.
  • elementos distintos frente a elementos no distintos (conjuntos múltiples).

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

[Actualizar]

Josh O''Brien sugiere que las 8 preguntas están relacionadas de doce maneras . De hecho, las preguntas "distintas" se incluyen de doce maneras, mientras que las preguntas "distintas" no están incluidas. De todos modos, es interesante comparar las 8 preguntas aquí con doce formas. Vea los comentarios para más lecturas.

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

Empezando a usar el arrangement

arrangements contienen 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 here .

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"

Compara con otros paquetes

Hay pocas ventajas de utilizar arrangements sobre los paquetes existentes.

  1. Marco integral: no es necesario utilizar diferentes paquetes para diferentes métodos.

  2. Es muy eficiente. Consulte here para ver algunos puntos de referencia.

  3. Es memoria eficiente, 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. 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, lo que puede ser deseado por algunos usuarios.