Combinaciones desordenadas en R

combinations

Question

Estoy buscando una función que me devuelva toda la combinación desordenada de un vector. p.ej

x<-c(''red'',''blue'',''black'')
uncomb(x)
[1]''red''
[2]''blue''
[3]''black''
[4]''red'',''blue''
[5]''blue'',''black''
[6]''red'',''black''
[7]''red'',''blue'',''black''

Supongo que hay una función en alguna biblioteca que hace esto, pero no puedo encontrarla. Estoy intentando con permutations de gtool pero no es la función que estoy buscando.

Answer 1

Fui redirigido aquí desde Listar todas las combinaciones con combn ya que este era uno de los objetivos de engaño. Esta es una vieja pregunta y la respuesta proporcionada por @RichScriven es muy agradable, pero quería darle a la comunidad algunas opciones más que posiblemente sean más naturales y más eficientes (las dos últimas).

Primero notamos que la salida es muy similar al conjunto de potencia . Al llamar a powerSet desde el paquete rje , vemos que, de hecho, nuestra salida coincide con cada elemento del conjunto de potencia, excepto el primer elemento que es equivalente al conjunto vacío :

x <- c("red", "blue", "black")
rje::powerSet(x)
[[1]]
character(0)   ## empty set equivalent

[[2]]
[1] "red"

[[3]]
[1] "blue"

[[4]]
[1] "red"  "blue"

[[5]]
[1] "black"

[[6]]
[1] "red"   "black"

[[7]]
[1] "blue"  "black"

[[8]]
[1] "red"   "blue"  "black"

Si no desea el primer elemento, puede agregar fácilmente un [-1] al final de su llamada de función de la siguiente manera: rje::powerSet(x)[-1] .

Las siguientes dos soluciones son de los arrangements paquetes más nuevos y RcppAlgos (soy el autor), que ofrecerán al usuario grandes ganancias en eficiencia. Ambos paquetes son capaces de generar combinaciones de Multisets .

¿Porque es esto importante?

Se puede demostrar que hay una asignación uno a uno del conjunto de potencia de A a todas las combinaciones del multiset c(rep(emptyElement, length(A)), A) elegir length(A) , donde emptyElement es un representación del conjunto vacío (como cero o un espacio en blanco). Con esto en mente, observe:

library(arrangements)
combinations(x = c("",x), k = 3, freq = c(2, rep(1, 3)))
     [,1]  [,2]   [,3]   
[1,] ""    ""     "red"  
[2,] ""    ""     "blue" 
[3,] ""    ""     "black"
[4,] ""    "red"  "blue" 
[5,] ""    "red"  "black"
[6,] ""    "blue" "black"
[7,] "red" "blue" "black"

library(RcppAlgos)
comboGeneral(c("",x), 3, freqs = c(2, rep(1, 3)))
     [,1]    [,2]    [,3]   
[1,] ""      ""      "black"
[2,] ""      ""      "blue" 
[3,] ""      ""      "red"  
[4,] ""      "black" "blue" 
[5,] ""      "black" "red"  
[6,] ""      "blue"  "red"  
[7,] "black" "blue"  "red"

Si no le gusta tratar con elementos y / o matrices en blanco, también puede devolver una lista haciendo uso de lapply .

lapply(seq_along(x), comboGeneral, v = x)
[[1]]
     [,1]   
[1,] "black"
[2,] "blue" 
[3,] "red"  

[[2]]
     [,1]    [,2]  
[1,] "black" "blue"
[2,] "black" "red" 
[3,] "blue"  "red" 

[[3]]
     [,1]    [,2]   [,3] 
[1,] "black" "blue" "red"


lapply(seq_along(x), combinations, n = length(x), x = x)
[[1]]
     [,1]   
[1,] "red"  
[2,] "blue" 
[3,] "black"

[[2]]
     [,1]   [,2]   
[1,] "red"  "blue" 
[2,] "red"  "black"
[3,] "blue" "black"

[[3]]
     [,1]  [,2]   [,3]   
[1,] "red" "blue" "black"

Ahora mostramos que los dos últimos métodos son mucho más eficientes (Nota: do.call(c, y simplify = FALSE de la respuesta proporcionada por @RichSciven para comparar la generación de resultados similares. También rje::powerSet para buena medida):

set.seed(8128)
bigX <- sort(sample(10^6, 20)) ## With this as an input, we will get 2^20 - 1 results.. i.e. 1,048,575
library(microbenchmark)
microbenchmark(powSetRje = powerSet(bigX),
               powSetRich = lapply(seq_along(bigX), combn, x = bigX),
               powSetArrange = lapply(seq_along(bigX), function(y) combinations(x = bigX, k = y)),
               powSetAlgos = lapply(seq_along(bigX), comboGeneral, v = bigX),
               unit = "relative")

Unit: relative
          expr       min        lq      mean    median       uq      max neval
     powSetRje 52.992681 15.055038 11.091203 13.586952 8.860661 7.347368   100
    powSetRich 58.679666 14.864760 10.914700 13.198179 8.675812 6.017437   100
 powSetArrange  1.042766  1.062227  1.071404  1.098491 1.126971 1.044827   100
   powSetAlgos  1.000000  1.000000  1.000000  1.000000 1.000000 1.000000   100

Aún más, los arrangements vienen equipados con un argumento llamado type que permite al usuario elegir un formato particular para su salida. Uno de ellos es type = "l" para la lista. Es similar a la configuración simplify = FALSE en combn y nos permite obtener resultados como el de powerSet . Observar:

do.call(c, lapply(seq_along(x), combinations, n = length(x), x = x, type = "l"))
[[1]]
[1] "red"

[[2]]
[1] "blue"

[[3]]
[1] "black"

[[4]]
[1] "red"  "blue"

[[5]]
[1] "red"   "black"

[[6]]
[1] "blue"  "black"

[[7]]
[1] "red"   "blue"  "black"

Y los puntos de referencia:

microbenchmark(powSetRje = powerSet(bigX)[-1],
               powSetRich = do.call(c, lapply(seq_along(bigX), combn, x = bigX, simplify = FALSE)),
               powSetArrange = do.call(c, lapply(seq_along(bigX), combinations, n = length(bigX), x = bigX, type = "l")),
               times = 15, unit = "relative")
Unit: relative
          expr      min       lq     mean   median       uq      max neval
     powSetRje 4.925559 4.433365 4.013872 3.893674 3.819344 3.609616    15
    powSetRich 5.732216 4.975508 4.542482 4.564668 4.288592 4.003765    15
 powSetArrange 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000    15

Answer 2

Podría aplicar una secuencia de la longitud de x sobre el argumento m de la función combn() .

x <- c("red", "blue", "black")
do.call(c, lapply(seq_along(x), combn, x = x, simplify = FALSE))
# [[1]]
# [1] "red"
# 
# [[2]]
# [1] "blue"
# 
# [[3]]
# [1] "black"
# 
# [[4]]
# [1] "red"  "blue"
# 
# [[5]]
# [1] "red"   "black"
# 
# [[6]]
# [1] "blue"  "black"
# 
# [[7]]
# [1] "red"   "blue"  "black"

Si prefiere un resultado de matriz, puede aplicar stringi::stri_list2matrix() a la lista anterior.

stringi::stri_list2matrix(
    do.call(c, lapply(seq_along(x), combn, x = x, simplify = FALSE)),
    byrow = TRUE
)
#      [,1]    [,2]    [,3]   
# [1,] "red"   NA      NA     
# [2,] "blue"  NA      NA     
# [3,] "black" NA      NA     
# [4,] "red"   "blue"  NA     
# [5,] "red"   "black" NA     
# [6,] "blue"  "black" NA     
# [7,] "red"   "blue"  "black"