在 R 中生成由节点函数递归定义的 K-Nary 树 [英] Generating A K-Nary Tree In R Recursively Defined By a Node-Wise Function

问题描述

如何生成具有未知数量节点的树，每个节点都有未知且不同数量的子节点，条件是给定父节点的子节点列表由某些 fun(parent)?请注意，我正在使用 cran 中的 library(data.tree) 来创建树层次结构.

树总是以给定父向量定义的节点开始.节点的数量总是有限的.每个节点将与根节点具有相同的长度.

我试图脱离上下文从一般意义上提出问题，但它过于笼统，无法提供明确的反馈.因此，这里是目前不完全存在的脚本:

require(data.tree)#还需要生成脚本(底部链接)才能运行# 帮助函数将节点作为具有唯一名称的父节点的子节点插入我=1assn <- 函数(子，父变量名){child<-paste(child,collapse="")nam <- paste("v", i, sep = "")# 将节点分配给名为 vi 的变量# 并使树全局化，以便在函数外部可见分配(南，parentvarname$AddChild(child)，envir = .GlobalEnv)noquote(nam)->a我+1a #输出子变量名vi，以便递归}cdrtree<- 函数(根){#分配根v0 <- Node$new(root) #将根分配给树的根node<-root #rename 变量以在下一步中清晰起见Kidparentname<-v0 #recursion 从 v0 开始have.kids<-function(node){ #这很不幸是无性繁殖...for(pointer in cdrpointers(node)){ #可变数量的指针是#用于确定下一个节点(如果有的话) cdrmovecdrmove(node,pointer)->newkid #制作一个孩子assn(newkid,kidparentname) #在树层次结构中输入这个节点#获取下一次迭代的newkid名称并将名称写入树Kidparentname<-assn(newkid,kidparentname)node<-newkid #rename 下一次迭代的节点变量have.kids(newkid) #recurse，问题可能出在这里}return(v0) #返回树(如果代码有效...)}}

在可能的根节点节点上运行脚本给出了一个奇怪的结果:

<代码>>cdrtree(c(1,-2,3))>cdrtree(c(1,-2,3))->a>一种function(node){ #不幸的是这是无性繁殖...for(pointer in cdrpointers(node)){ #可变数量的指针是... #所有代码如上...}<环境:0x00000000330ee348>

如果您想要一个真正的工作示例，您可以从

解决方案

我认为您的函数没有按预期工作.例如，使用您的起始值，

lapply(cdrpointers(c(1,-2,3)), function(i) cdrmove(c(1,-2,3), i))[[1]][1] 1 2 3[[2]][1] 1 2 3

但是，假设这些工作.您可以尝试以下方法并确定它们是否被错误地使用.

## 唯一命名节点，不要像分配给 .Globalenv 一样## 你在 `assn` 中，这不会工作，因为 `i` 没有被递增.## 你可以在全局中增加 `i`，但是，相反，## 我会将`i` 封装在函数的parent.frame 中，避免可能发生的冲突nodeNamer <- function() {我＜- 0## 注意:`i` 使用 `<<-` 在这个函数的范围之外递增函数(节点)sprintf(v%g"，(i <<- i+1))}##加载你的函数，没仔细看这些，##所以只是假设他们工作源(文件=https://raw.githubusercontent.com/zediiiii/CDS/master/Generating%20Scripts.r")cdrtree <- 函数(根值){root <- Node$new('root') # 分配根root$value <- root.value # 似乎是值与名称的分离name_node <- nodeNamer() # 初始化节点计数器以命名节点## 定义你的递归辅助函数## 注意:你可以不用这个，让 `cdrtree` 有一个额外的## 参数，说 tree=NULL.但是，我认为分离很好.have.kids <- 函数(节点){## 这个函数(`cdrpointers`)需要工作，它应该返回一个0长度的列表，而不是打印## 一些东西，然后如果没有值则出错##(或者如果这是你想要的，则抛出并错误消息)指针 <- tryCatch({cdrpointers(node$value)}, error=function(e) return(list()))if (!length(pointers)) return()for(指针中的指针){child_val <- cdrmove(node$value, pointer) # 这总是有效吗?child <- Node$new(name_node()) # 给节点一个名字child$value <- child_valchild <- node$AddChildNode(child)Recall(child) # 和孩子一起递归}}have.kids(root)返回(根)}图书馆(数据树)res <- cdrtree(root.value=c(1,-2,3))

How can I generate a tree with an unknown number of nodes, each of which have an unknown and varying number of children, with the condition that a list of the child nodes for a given parent node is generated by some fun(parent)? Note that I'm using library(data.tree) from cran to make my tree hierarchy.

The tree will always begin with a node defined by a given parent vector. There will always be a finite amount of nodes. Every node will have the same length as the root node.

I've tried to create the question in a general sense out of context, but it has just been too general to provide definitive feedback. Accordingly, here is the script that is presently not quite there:

require(data.tree)
#also requires Generating Scripts (link at bottom) to run
# Helper function to insert nodes as children of parents with unique names
i=1
assn <- function(child,parentvarname){
    child<-paste(child,collapse=" ")
    nam <- paste("v", i, sep = "")

    # assign node to variable called vi  
    # and make the tree global so it can be seen outside the function
    assign(nam, parentvarname$AddChild(child),envir = .GlobalEnv) 
    noquote(nam)->a
    i+1
    a          #output the child variable name vi for the sake of recursion
}

cdrtree<- function(root){
    #assign root
    v0 <- Node$new(root)  #assign root to the root of the tree
    node<-root             #rename variable for clarity in next step
    kidparentname<-v0      #recursion starts at v0

    have.kids<-function(node){   #this is unfortunately asexual reproduction...
                for(pointer in cdrpointers(node)){ #A variable number of pointers are
                    #used to determine the next node(s) if any with function cdrmove

                    cdrmove(node,pointer)->newkid #make a child
                    assn(newkid,kidparentname) #enter this node in the tree hierarchy

                    #get the name of newkid for next iteration and write name to tree
                    kidparentname<-assn(newkid,kidparentname)
                    node<-newkid    #rename node variable for the next iteration
                    have.kids(newkid)  #recurse, likely the problem is here
                }

    return(v0) #return the tree (if the code works...)
        }
}

Running the script on a possible root node node gives a strange result:

> cdrtree(c(1,-2,3))
> cdrtree(c(1,-2,3))->a
> a
function(node){   #this is unfortunately asexual reproduction...
                for(pointer in cdrpointers(node)){ #A variable number of pointers are
                    ... #all code as written above ...
}
<environment: 0x00000000330ee348>

If you want a true working example, you can grab and source "Generating Scripts.R" from here and run it with any signed permutation of 1:n with n>2 as an argument similar to my example.

To be extra clear, the tree with root node c(1,-2,3) would hypothetically look something like this:

解决方案

I don't think your function are working as expected. For example, using your starting value,

lapply(cdrpointers(c(1,-2,3)), function(i) cdrmove(c(1,-2,3), i))
[[1]]
[1] 1 2 3

[[2]]
[1] 1 2 3

But, assuming those work. you could try the following and determine if they are being used incorrectly.

## Name nodes uniquely, dont be assigning to the .Globalenv like
## you are in `assn`, which wont work becuse `i` isn't being incremented.
## You could invcrement `i` in the global, but, instead,
## I would encapsulate `i` in the function's parent.frame, avoiding possible conflicts
nodeNamer <- function() {
    i <- 0
    ## Note: `i` is incremented outside of the scope of this function using `<<-`
    function(node) sprintf("v%g", (i <<- i+1))
}

## Load your functions, havent looked at these too closely,
## so just gonna assume they work
source(file="https://raw.githubusercontent.com/zediiiii/CDS/master/Generating%20Scripts.r")

cdrtree <- function(root.value) {
    root <- Node$new('root')  # assign root
    root$value <- root.value  # There seems to be a separation of value from name
    name_node <- nodeNamer()   # initialize the node counter to name the nodes

    ## Define your recursive helper function
    ## Note: you could do without this and have `cdrtree` have an additional
    ## parameter, say tree=NULL.  But, I think the separation is nice.
    have.kids <- function(node) {
        ## this function (`cdrpointers`) needs work, it should return a 0 length list, not print
        ## something and then error if there are no values
        ## (or throw and error with the message if that is what you want)
        pointers <- tryCatch({cdrpointers(node$value)}, error=function(e) return( list() ))
        if (!length(pointers)) return()
        for (pointer in pointers) {
            child_val <- cdrmove(node$value, pointer)  # does this always work?
            child <- Node$new(name_node())             # give the node a name
            child$value <- child_val
            child <- node$AddChildNode(child)
            Recall(child)                              # recurse with child
        }
    }
    have.kids(root)
    return( root )
}

library(data.tree)
res <- cdrtree(root.value=c(1,-2,3))

这篇关于在 R 中生成由节点函数递归定义的 K-Nary 树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！