I think i got it.
I made an auxiliary function to check the sub-trees that i was storing,
this way i guarantee that i don't repeat.
Efficiency is pretty bad, but it works right, i hope. I posted here, in
case someone wants the see it. Might be good for an example in a class,
maybe.
##########################################################################################
#the auxiliary function, to check on auxiliary and temporary lists
checa_lista<-function(lista,vetor) {
if(length(lista)==0) {
return(FALSE)
} else {
if(sum(sapply(lapply(lista,function(x) { vetor%in%x }) ,prod))>0)
{
return(TRUE)
} else {
return(FALSE)
}
}
}
#it check if the "ingredients are already there
teste1<-list()
teste2<-list(c(1,2),c(1,3),c(2,3))
checa_lista(teste1,c(2,1))
checa_lista(teste2,c(2,1))
#and the same function of before, now doing this check
todas_arvores<-function(entrada) {
#Transform the vector of names in a list with one element
saida<-list(entrada)
#In the fisrt iteration, the first element of this list will have
length==entrada,
#we will iterate until it is one full string, just one element
while(length(saida[[1]])!=1) {
#auxiliar list to receave the subtrees
aux<-list()
#the fisrt iteration this is one, but increase within each
interation
for(i in 1:length(saida)) {
#another temporararie container for subtrees, here to be able
to iterate though all the saida length
temporario<-list()
#Do all possible 2 combinarions, unite 2 species, ou one
species and a subtree(now a greater string)
#(a,b) for example, after the first iteration and reserve here
combinacoes<-combn(saida[[i]],2)
#now for all combinations i glue the combination with paste,
like (a,b), and generate a vector with what is
#still missing, look the %in% check
for(j in 1:ncol(combinacoes)) {
tempo<-c(saida[[i]][!saida[[i]]%in%combinacoes[,j]],paste("(",combinacoes[1,j],",",combinacoes[2,j],")",sep=""))
if(!(checa_lista(aux,tempo)||checa_lista(temporario,tempo))) {
temporario<-c(temporario,list(tempo))
}
}
#for each element os saida, i store the results here
aux<-c(aux,temporario)
}
#at the end, i store everything at saida again, now we are ready to
test the while condition again, but now i
#hope that there will be a vector of n-1 elements from the when we
started this iteration.
saida<-aux
}
#just to produce a better output, i unlist and add the ; in the end, to
use read.tree from ape
saida<-unlist(saida)
saida<-sapply(saida,function(arvore)
{paste(arvore,";",sep="")},USE.NAMES = FALSE)
return(saida)
}
#example of use
arvores<-todas_arvores(paste("sp",1:4))
arvores
library(ape)
#just a plot to see what i'm trying
raiz<-sqrt(length(arvores))
par(mar=c(2,1,2,2))
layout(matrix(1:c(ceiling(raiz)*ceiling(raiz)),nrow=ceiling(raiz),ncol=ceiling(raiz),byrow=T))
for(i in 1:length(arvores)) {
plot(read.tree(text=arvores[i]),cex=1)
title(paste("Árvore",i))
}
##########################################################################################
I read on wikipedia how to calculate the number of expected trees, as a
double factorial http://en.wikipedia.org/wiki/Unrooted_binary_tree
Thanks for the atttention.
2014-03-08 9:47 GMT-04:00 Klaus Schliep <klaus.schl...@gmail.com>:
> There is a function allTrees in phangorn, which computes all binary trees.
>
> Cheers,
> Klaus
>
>
> On Sat, Mar 8, 2014 at 1:40 PM, Augusto Ribas <ribas....@gmail.com> wrote:
>
>> Hello.
>>
>> I'm trying to do a function to generate all possible trees for N species.
>> I think i almost got it, but there is something that i'm missing.
>>
>> ##################################
>> todas_arvores<-function(entrada) {
>> #Transform the vector of names in a list with one element
>> saida<-list(entrada)
>> #In the fisrt iteration, the first element of this list will have
>> length==entrada,
>> #we will iterate until it is one full string, just one element
>> while(length(saida[[1]])!=1) {
>> #auxiliar list to receive the sub-trees
>> aux<-list()
>> #the first iteration this is one, but increase within each
>> iteration
>> for(i in 1:length(saida)) {
>> #another temporarily container for sub-trees, here to be able
>> to iterate though all the saida length
>> temporario<-list()
>> #Do all possible 2 combinations, unite 2 species, or one
>> species and a sub-tree(now a greater string)
>> #(a,b) for example, after the first iteration and reserve here
>> combinacoes<-combn(saida[[i]],2)
>> #now for all combinations i glue the combination with paste,
>> like (a,b), and generate a vector with what is
>> #still missing, look the %in% check
>> for(j in 1:ncol(combinacoes)) {
>>
>>
>> temporario[[j]]<-c(saida[[i]][!saida[[i]]%in%combinacoes[,j]],paste("(",combinacoes[1,j],",",combinacoes[2,j],")",sep=""))
>> }
>> #for each element os saida, i store the results here
>> aux<-c(aux,temporario)
>> }
>> #at the end, i store everything at saida again, now we are ready
>> to
>> test the while condition again, but now i
>> #hope that there will be a vector of n-1 elements from the when we
>> started this iteration.
>> saida<-aux
>> }
>> #just to produce a better output, i unlist and add the ; in the end,
>> to
>> use read.tree from ape
>> saida<-unlist(saida)
>> saida<-sapply(saida,function(arvore)
>> {paste(arvore,";",sep="")},USE.NAMES = FALSE)
>> return(saida)
>> }
>>
>>
>> #example of use
>> arvores<-todas_arvores(paste("sp",1:4))
>> arvores
>>
>> library(ape)
>>
>> #example of wrong output
>> dist.topo(read.tree(text=arvores[1]),read.tree(text=arvores[16]))
>>
>>
>> #just a plot to see what i'm trying
>> raiz<-sqrt(length(arvores))
>> par(mar=c(1,1,1,2))
>>
>> layout(matrix(1:c(floor(raiz)*ceiling(raiz)),nrow=floor(raiz),ncol=ceiling(raiz),byrow=T))
>>
>> for(i in 1:length(arvores)) {
>> plot(read.tree(text=arvores[i]),cex=1)
>> title(paste("Tree",i))
>> }
>>
>> ##################################
>>
>>
>> as i see, here
>>
>> for(j in 1:ncol(combinacoes)) {
>>
>>
>> temporario[[j]]<-c(saida[[i]][!saida[[i]]%in%combinacoes[,j]],paste("(",combinacoes[1,j],",",combinacoes[2,j],")",sep=""))
>> }
>>
>> i would need to test if the sub-tree(elements of the vector) is already
>> present in the aux list, to evade reintroduce copy of the same tree, but
>> i don't know how.
>> something like, there will be a moment, for 4 species that there will be a
>> element in aux like
>> (sp 1,sp 2) (sp 3,sp 4)
>>
>> this time i dont want to put this one on temporario
>> (sp 3,sp 4) (sp 1,sp 2)
>>
>> because there is already an element like this on aux, just the inverse
>> order, as i keep both i produce 2 equal trees in the end.
>>
>>
>> I don't know if maybe there is a simple algorithm to do this, something
>> like apply a modification to a starting tree, any suggestion?
>>
>> Another question is, i need to produce the species catalan number of trees
>> right? Is this how to predict the number of possible trees?
>>
>> Best Wishes, Augusto Ribas
>>
>> --
>> Grato
>> Augusto C. A. Ribas
>>
>> Site Pessoal: http://recologia.com.br/ <http://augustoribas.heliohost.org
>> >
>>
>> Github: https://github.com/Squiercg
>> Lattes: http://lattes.cnpq.br/7355685961127056
>>
>> [[alternative HTML version deleted]]
>>
>> _______________________________________________
>> R-sig-phylo mailing list - R-sig-phylo@r-project.org
>> https://stat.ethz.ch/mailman/listinfo/r-sig-phylo
>> Searchable archive at
>> http://www.mail-archive.com/r-sig-phylo@r-project.org/
>>
>
>
>
> --
> Klaus Schliep
> Phylogenomics Lab at the University of Vigo, Spain
> http://darwin.uvigo.es/kschliep/
>
>
--
Grato
Augusto C. A. Ribas
Site Pessoal: http://recologia.com.br/ <http://augustoribas.heliohost.org>
Github: https://github.com/Squiercg
Lattes: http://lattes.cnpq.br/7355685961127056
[[alternative HTML version deleted]]
_______________________________________________
R-sig-phylo mailing list - R-sig-phylo@r-project.org
https://stat.ethz.ch/mailman/listinfo/r-sig-phylo
Searchable archive at http://www.mail-archive.com/r-sig-phylo@r-project.org/
