Путь к индексу всех элементов списка

Question

Как получить индексный путь для всех элементов списка?

tree <- list(1:6,b=list(a=20:23,b=28),c=c("a","b")) 

Как получить адресную информацию из существующего списка дерева для всех листьев? Возвращаемое значение в виде списка векторов, как показано ниже.

ret <- list(leaf1=c(1,1), .... ,leaf7=c(2,1,1), .... ,leaf13=c(3,2)) 
# tree[[c(2,1,1)]] should return 20 then. 
# so the leaf7 value is indexing vector for tree$b$a[1] in another notation. 
# so the tree$b$a[1] is same as tree[[ret$leaf7]] 
# and so the object ret is then sort of a map of list "tree" 

Answer 1

Ваша основная глубина первого поиска. Компонента Map/unlist состоит в том, чтобы сохранить список результатов равным, и, таким образом, результат уровня листа в предложении else должен быть завернут в список. idx содержит текущий индекс в структуре, а acc - накопленные индексы листьев.

index.leaves <- function(root) { 
    walk <- function(node,idx,acc) { 
    if(length(node)>1) { 
     r<-Map(function(child,i) walk(child,c(idx,i),acc),node,seq_along(node)) 
     unlist(r,recursive=FALSE) 
    } 
    else { 
     list(c(acc,idx)) 
    } 
    } 
    walk(root,NULL,c()) 
} 

С выборки данных

str(index.leaves(tree)) 

 
List of 13 
$  : num [1:2] 1 1 
$  : num [1:2] 1 2 
$  : num [1:2] 1 3 
$  : num [1:2] 1 4 
$  : num [1:2] 1 5 
$  : num [1:2] 1 6 
$ b.a1: num [1:3] 2 1 1 
$ b.a2: num [1:3] 2 1 2 
$ b.a3: num [1:3] 2 1 3 
$ b.a4: num [1:3] 2 1 4 
$ b.b : num [1:2] 2 2 
$ c.a : num [1:2] 3 1 
$ c.b : num [1:2] 3 2 

Answer 2

Пару рекурсивных подходов, которые используют другой способ для выравнивания списка результатов:

подход 1. Глубина первого поиска; как только мы достигнем дна, сохраним результат в переменной верхнего уровня L.

nametree <- function(X) { 
    L <- NULL 

    rec <- function(X, prefix = NULL) { 
    if(length(X) == 1) {L <<- c(L,list(prefix)); return()}  
    sapply(seq_along(X), function(i) rec(X[[i]], c(prefix,i))) 
    } 

    rec(X) 
    L 
} 

подход 2. Глубина первого поиска; векторы с индексами сохраняются через return. В этом случае результатом является вложенный список, поэтому он должен быть сплющен, что достигается комбинацией rapply/unlist/split.

nametree2 <- function(X) { 

    rec <- function(X, prefix = NULL) { 
    if(length(X) == 1) return(prefix)  
    lapply(seq_along(X), function(i) rec(X[[i]], c(prefix,i))) 
    } 

    z <- rec(X) 

    # Convert nested list into a simple list 
    z2 <- rapply(z,length) 
    split(unlist(z),rep(seq_along(z2),z2)) 
} 

z <- nametree(tree) 
z2 <- nametree2(tree) 

Оба подхода возвращает один и тот же результат, который может быть использован для индексации оригинального tree списка:

> tree[[z[[7]]]] 
[1] 20 
> tree[[z2[[7]]]] 
[1] 20