¿Cómo crear todas las combinaciones de una lista anidada mientras se preserva la estructura usando R?

recursion

Question

Dada una lista anidada, ¿cómo crear todas las listas posibles a partir de sus elementos, mientras se preserva la estructura de la lista anidada?

Lista anidada:

l = list(
a = list(
b = 1:2
),
c = list(
d = list(
e = 3:4,
f = 5:6
)
),
g = 7
)

Salida deseada: todas las combinaciones posibles de los elementos de l , conservando la estructura, por ejemplo:

# One possible output:
list(
a = list(
b = 1
),
c = list(
d = list(
e = 3,
f = 5
)
),
g = 7
)
# Another possible output:
list(
a = list(
b = 1
),
c = list(
d = list(
e = 4,
f = 5
)
),
g = 7
)

Mi enfoque hasta ahora es:

1. aplanar la lista (por ejemplo, como se discutió en esta respuesta )
2. expand.grid() y obtiene una matriz donde cada fila representa una combinación única
3. analizar cada fila de la matriz resultante y reconstruir la estructura a partir de los names() usando expresiones regulares

Estoy buscando un enfoque menos engorroso porque no tengo garantía de que los nombres de los elementos de la lista no cambien.

Answer 1

Al reunir las excelentes respuestas de Ben Nutzer y Joris Chau , tenemos una manera de crear todas las combinaciones posibles de una lista anidada, independientemente de si algunos componentes de la sublista tienen una longitud desigual.

Poner juntos como una función:

list.combine <- function(input) {
# Create list skeleton.
skeleton <- rapply(input, head, n = 1, how = "list")
# Create storage for the flattened list.
flattened = list()
# Flatten the list.
invisible(rapply(input, function(x) {
flattened <<- c(flattened, list(x))
}))
# Create all possible combinations from list elements.
combinations <- expand.grid(flattened, stringsAsFactors = FALSE)
# Create list for storing the output.
output <- apply(combinations, 1, relist, skeleton = skeleton)
return(output)
}

Nota: Si existe un tipo de carácter en los componentes de la sublista, todo se convertirá en un carácter. Por ejemplo:

# Input list.
l <- list(
a = "string",
b = list(
c = 1:2,
d = 3
)
)
# Applying the function.
o <- list.combine(l)
# View the list:
str(o)
# List of 2
# $ :List of 2
# ..$ a: chr "string"
# ..$ b:List of 2
# .. ..$ c: chr "1"
# .. ..$ d: chr "3"
# $ :List of 2
# ..$ a: chr "string"
# ..$ b:List of 2
# .. ..$ c: chr "2"
# .. ..$ d: chr "3"

Una forma lenta de evitar esto es relist a relist dentro de un ciclo que mantendrá los datos en un marco de datos 1x1 . Acceder al marco de datos como df[, 1] dará un vector de longitud 1 del tipo original como elemento en la lista de entrada. Por ejemplo:

list.combine() actualizada.combine list.combine() :

list.combine <- function(input) {
# Create list skeleton.
skeleton <- rapply(input, head, n = 1, how = "list")
# Create storage for the flattened list.
flattened = list()
# Flatten the list.
invisible(rapply(input, function(x) {
flattened <<- c(flattened, list(x))
}))
# Create all possible combinations from list elements.
combinations <- expand.grid(flattened, stringsAsFactors = FALSE)
# Create list for storing the output.
output <- list()
# Relist and preserve original data type.
for (i in 1:nrow(combinations)) {
output[[i]] <- retain.element.type(relist(flesh = combinations[i, ], skeleton = skeleton))
}
return(output)
}

Entonces el retain.element.type() :

retain.element.type <- function(input.list) {
for (name in names(input.list)) {
# If the element is a list, recall the function.
if(inherits(input.list[[name]], "list")) {
input.list[[name]] <- Recall(input.list[[name]])
# Else, get the first element and preserve the type.
} else {
input.list[[name]] <- input.list[[name]][, 1]
}
}
return(input.list)
}

Ejemplo:

# Input list.
l <- list(
a = "string",
b = list(
c = 1:2,
d = 3
)
)
# Applying the updated function to preserve the data type.
o <- list.combine(l)
# View the list:
str(o)
# List of 2
# $ :List of 2
# ..$ a: chr "string"
# ..$ b:List of 2
# .. ..$ c: int 1
# .. ..$ d: num 3
# $ :List of 2
# ..$ a: chr "string"
# ..$ b:List of 2
# .. ..$ c: int 2
# .. ..$ d: num 3

Answer 2

Combinando la brillante respuesta de Ben Nutzer y el brillante comentario de Joris Chau , la respuesta se convertirá en una frase:

apply(expand.grid(data.frame(l)), 1L, relist, skeleton = rapply(l, head, n = 1L, how = "list")) 

Crea una lista de listas con tantos elementos como filas devueltas por expand.grid() . El resultado se visualiza mejor con la salida de str() :

str(apply(expand.grid(data.frame(l)), 1L, relist, skeleton = rapply(l, head, n = 1L, how = "list")))

List of 16
$ :List of 3
..$ a:List of 1
.. ..$ b: num 1
..$ c:List of 1
.. ..$ d:List of 2
.. .. ..$ e: num 3
.. .. ..$ f: num 5
..$ g: num 7
$ :List of 3
..$ a:List of 1
.. ..$ b: num 2
..$ c:List of 1
.. ..$ d:List of 2
.. .. ..$ e: num 3
.. .. ..$ f: num 5
..$ g: num 7
...
...
...
$ :List of 3
..$ a:List of 1
.. ..$ b: num 2
..$ c:List of 1
.. ..$ d:List of 2
.. .. ..$ e: num 4
.. .. ..$ f: num 6
..$ g: num 7

Answer 3

La función relist de utils parece estar diseñada para esta tarea:

rl <- as.relistable(l)
r <- expand.grid(data.frame(rl), KEEP.OUT.ATTRS = F)
> head(r, 5)
b c.d.e c.d.f g
1 1 3 5 7
2 2 3 5 7
3 1 4 5 7
4 2 4 5 7
5 1 3 6 7

Guarda la estructura de la lista ( skeleton ). Esto significa que ahora se pueden manipular los datos dentro de la lista anidada y reasignarlos a la estructura ( flesh ). Aquí con la primera fila de la matriz expandida.

r <- rep(unname(unlist(r[1,])),each = 2)
l2 <- relist(r, skeleton = rl)
> l2
$a
$a$b
[1] 1 1
$c
$c$d
$c$d$e
[1] 3 3
$c$d$f
[1] 5 5
$g
[1] 7
attr(,"class")
[1] "relistable" "list" 

Tenga en cuenta que, dado que la estructura se mantiene igual, necesito proporcionar la misma cantidad de elementos que en la lista original. Esta es la razón por la que usamos rep para repetir el elemento dos veces Supongo que también se podría llenar con NA .

Para cada combinación posible, repita a través de r (expandido):

lapply(1:nrow(r), function(x)
relist(rep(unname(unlist(r[x,])),each = 2), skeleton = rl))

Answer 4

Longitudes desiguales de sublista

Aquí hay un enfoque, que se extiende a las respuestas de Uwe y Ben, que también funciona para longitudes arbitrarias de sublistas. En lugar de llamar a expand.grid en data.frame(l) , primero aplana l a una lista de un solo nivel y luego llama a expand.grid en ella:

## skeleton
skel <- rapply(l, head, n = 1L, how = "list")
## flatten to single level list
l.flat <- vector("list", length = length(unlist(skel)))
i <- 0L
invisible(
rapply(l, function(x) {
i <<- i + 1L
l.flat[[i]] <<- x
})
)
## expand all list combinations
l.expand <- apply(expand.grid(l.flat), 1L, relist, skeleton = skel)
str(l.expand)
#> List of 12
#> $ :List of 3
#> ..$ a:List of 1
#> .. ..$ b: num 1
#> ..$ c:List of 1
#> .. ..$ d:List of 2
#> .. .. ..$ e: num 3
#> .. .. ..$ f: num 5
#> ..$ g: num 7
#> ...
#> ...
#> $ :List of 3
#> ..$ a:List of 1
#> .. ..$ b: num 2
#> ..$ c:List of 1
#> .. ..$ d:List of 2
#> .. .. ..$ e: num 4
#> .. .. ..$ f: num 7
#> ..$ g: num 7

Datos

Modifiqué ligeramente la estructura de datos, de modo que los componentes de la sublista e y f tienen una longitud desigual.

l <- list(
a = list(
b = 1:2
),
c = list(
d = list(
e = 3:4,
f = 5:7
)
),
g = 7
)
## calling data.frame on l does not work
data.frame(l)
#> Error in (function (..., row.names = NULL, check.rows = FALSE, check.names = TRUE, : arguments imply differing number of rows: 2, 3