Вопрос:

Как создать все комбинации из вложенного списка при сохранении структуры с помощью R?

r list recursion

205 просмотра

4 ответа

901 Репутация автора

При наличии вложенного списка, как создать все возможные списки из его элементов, сохранив при этом структуру вложенного списка?

Вложенный список:

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

Желаемый результат: все возможные комбинации элементов lпри сохранении структуры, например:

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

Мой подход до сих пор заключается в следующем:

  1. выровнять список (например, как обсуждалось в этом ответе )
  2. expand.grid() и получить матрицу, где каждая строка представляет собой уникальную комбинацию
  3. разбирать каждую строку полученной матрицы и восстанавливать структуру по names()регулярным выражениям

Я ищу менее громоздкий подход, потому что не могу гарантировать, что имена элементов списка не изменятся.

Автор: Mihai Источник Размещён: 11.08.2019 07:08

Ответы (4)


7 плюса

279 Репутация автора

relistФункция от , utilsкажется, предназначена для решения этой задачи:

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

Сохраняет структуру списка ( skeleton). Это означает, что теперь можно манипулировать данными во вложенном списке и переназначать их в структуру ( flesh). Здесь с первой строки развернутой матрицы.

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"  

Обратите внимание, что, поскольку структура остается прежней, мне нужно указать то же количество элементов, что и в исходном списке. Вот почему используется repдля повторения элемента дважды. NAДумаю, можно было бы его заполнить .

Для каждой возможной комбинации выполните итерацию r(развернуто):

lapply(1:nrow(r), function(x) 
          relist(rep(unname(unlist(r[x,])),each = 2), skeleton = rl))
Автор: Ben Nutzer Размещён: 11.08.2019 08:05

5 плюса

25604 Репутация автора

Сочетая блестящий ответ Бена Натцера и блестящий комментарий Йориса Чау , ответ станет однострочным:

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

Он создает список списков с таким количеством элементов, сколько строк возвращено expand.grid(). Результат лучше визуализируется выводом 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 Размещён: 11.08.2019 09:19

2 плюса

1918 Репутация автора

Неравная длина подсписка

Вот подход, основанный на ответах Уве и Бена, который также работает для произвольных длин подсписков. Вместо вызова expand.gridна data.frame(l), первый расплющить lв список одноуровневой , а затем вызвать expand.gridна нем:

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

Данные

Я слегка модифицировали структуру данных, так что компоненты Подсписок eи fимеют разную длину.

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 Chau Размещён: 12.08.2019 06:39

0 плюса

901 Репутация автора

Собрав воедино замечательные ответы Бена Натцера и Йориса Чау , у нас есть способ создать все возможные комбинации из вложенного списка независимо от того, имеют ли некоторые компоненты подсписка неодинаковую длину.

Составить как функцию:

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

Примечание. Если в компонентах подсписка существует символьный тип, все будет приведено к символу. Например:

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

Один - медленный путь - это relistвнутри цикла, который будет поддерживать данные в 1x1кадре данных. Доступ к кадру данных as df[, 1]даст вектор длины 1 исходного типа в качестве элемента во входном списке. Например:

Обновлено 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)
}

Тогда 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)
}

Пример:

# 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 Размещён: 12.08.2019 02:01
Вопросы из категории :
32x32