2

假设给定 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）顺序的列表。

4

1 回答 1

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))
于 2012-06-18T22:30:39.053 回答