13

Given a nested list, how to create all possible lists from its elements, while preserving the structure of the nested list?

Nested list:

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

Desired output: all possible combinations of the elements of l, while preserving the structure, e.g.:

# 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
)

My approach so far is to:

  1. flatten the list (e.g., as discussed in this answer)
  2. expand.grid() and get a matrix where each row represents a unique combination
  3. parse every row of the resulting matrix and reconstruct the structure from the names() using regular expressions

I am looking for a less cumbersome approach because I have no guarantee that the names of the list elements will not change.

4 Answers 4

9

The relist function from utils seems to be designed for this task:

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

It saves the structure of the list (skeleton). This means one can now manipulate the data within the nested list and re-assign it into the structure (flesh). Here with the first row of the expanded matrix.

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"  

Note that since the structure stays the same, I need to supply the same amount of elements as in the original list. This is why used rep to repeat the element twice. One could also fill it with NA, I guess.

For every possible combination iterate through r (expanded):

lapply(1:nrow(r), function(x) 
          relist(rep(unname(unlist(r[x,])),each = 2), skeleton = rl))
7
  • 3
    You could use rl <- rapply(l, head, n = 1, how = "list") as skeleton to avoid the need for the duplicate elements
    – Joris C.
    Aug 11, 2019 at 8:24
  • That's way more elegant!
    – Ben Nutzer
    Aug 11, 2019 at 8:35
  • @BenNutzer that's brilliant! Would this also hold if say b and e have different lengths? I am still trying to understand your answer. As soon as I am sure about it, I will mark it accepted!
    – Mihai
    Aug 11, 2019 at 8:44
  • 4
    Combining Ben Nutzer's answer and Joris Chau's comment, the answer will become a one-liner: apply(expand.grid(data.frame(l)), 1L, relist, skeleton = rapply(l, head, n = 1L, how = "list")). It creates a list of lists with as many elements as rows returned by expand.grid().
    – Uwe
    Aug 11, 2019 at 9:10
  • 1
    @Mihai Good point! In principle it should work. With my original approach something unintentional is happening, so it will only work with @JorisChau's suggestion. However, if your list lengths are not only unequal but also not a multiple of the other lists, you cannot coerce it to a dataframe any longer without filling it with e.g. NA. Maybe wait for another answer that solves this issue.
    – Ben Nutzer
    Aug 11, 2019 at 9:29
5

Combining Ben Nutzer's brilliant answer and Joris Chau's brilliant comment, the answer will become a one-liner:

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

It creates a list of lists with as many elements as rows returned by expand.grid(). The result is better visualised by the output of 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
2

Unequal sublist lengths

Here is an approach --extending on Uwe and Ben's answers-- that also works for arbitrary sublist lengths. Instead of calling expand.grid on data.frame(l), first flatten l to a single-level list and then call expand.grid on it:

## 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

Data

I slightly modified the data structure, so that the sublist components e and f are of unequal length.

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
1
  • I like your approach! I put everything together in a function and added extra logic to preserve the data type in case a character exists somewhere in the sublist components (i.e., otherwise everything would be coerced to character). There is probably a faster way to retain the data type (i.e., compared see this)... but it seems to get the job done. Thanks!
    – Mihai
    Aug 12, 2019 at 14:08
1

Putting together the great answers from Ben Nutzer and Joris Chau, we have a way to create all possible combinations from a nested list, regardless of whether some sublist components are of unequal length.

Put together as a function:

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)
}

Note: If a character type exists in the sublist components, then everything will be coerced to a character. For example:

# 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"

One--slow--way around this is to relist within a loop which will maintain the data in a 1x1 dataframe. Accessing the dataframe as df[, 1] will give a vector of length 1 of the original type as the element in the input list. For example:

Updated 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)
}

Then the 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)
}

Example:

# 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.