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 に答える