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.

Mihai
  • 2,807
  • 4
  • 28
  • 53

4 Answers4

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))
Ben Nutzer
  • 1,082
  • 7
  • 15
  • 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 '19 at 08:24
  • That's way more elegant! – Ben Nutzer Aug 11 '19 at 08: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 '19 at 08:44
  • @JorisChau indeed, it helps nicely with the duplicated elements! – Mihai Aug 11 '19 at 08:46
  • 4
    Combining [Ben Nutzer's answer](https://stackoverflow.com/a/57448353/3817004) and [Joris Chau's comment](https://stackoverflow.com/questions/57448008/how-to-create-all-combinations-from-a-nested-list-while-preserving-the-structure#comment101372378_57448353), 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 '19 at 09: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 '19 at 09:29
  • @BenNutzer, [Joris Chau](https://stackoverflow.com/a/57456645/5252007) posted a variant that allows for varying lengths. I compiled everything [here](https://stackoverflow.com/a/57462680/5252007), including some extra logical to preserve the data type in case character types are present. As far as I am concerned, your solution answers the original question perfectly. – Mihai Aug 12 '19 at 14:24
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
Uwe
  • 41,420
  • 11
  • 90
  • 134
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
Joris C.
  • 5,721
  • 3
  • 12
  • 27
  • 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](https://stackoverflow.com/a/57462680/5252007))... but it seems to get the job done. Thanks! – Mihai Aug 12 '19 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
Mihai
  • 2,807
  • 4
  • 28
  • 53