在R中生成k个序数的所有二叉树R

Question

假设给定了R中的序数列表，我想要生成所有有序的二叉树作为< = 2列表的递归列表。

因此，例如，给出list(2,1,4,3)，输出将是：

list(list(1, list(2, list(3, 4))), 
    list(1, list(list(2, 3), 4)), 
    list(list(1, 2), list(3, 4)), 
    list(list(1, list(2, 3)), 4), 
    list(list(list(1, 2), 3), 4)) 

在树上上市并不重要的顺序。排序不是一个问题，但是我正在努力做一个有效的递归。我知道R递归很慢，但速度不是问题，因为我正在处理相当低的订单（< = 7）。

Answer 1

这个函数应该让你去。这需要你给它什么名单和输出的所有二叉树保持项目列表的顺序给了他们：

trees <- function(l) { 
    if (length(l) <= 1) 
     return(l) 
    if (length(l) <= 2) 
     return(list(l)) 

    unlist(lapply(2:(length(l)), function(i) { 
     left.trees <- trees(l[1:(i-1)]) 
     right.trees <- trees(l[i:length(l)]) 
     apply(expand.grid(1:length(left.trees), 1:length(right.trees)), 1, function(idx) { 
      list(left.trees[[idx[1]]], right.trees[[idx[2]]]) 
     }) 
    }), recursive=FALSE) 
} 

所以你给的例子：

> dput(trees(as.list(1:4))) 
list(list(1L, list(2L, list(3L, 4L))), list(1L, list(list(2L, 
    3L), 4L)), list(list(1L, 2L), list(3L, 4L)), list(list(1L, 
    list(2L, 3L)), 4L), list(list(list(1L, 2L), 3L), 4L))