Quizá estoy diciendo una obviedad, pero ¿eso no es ordenar topológicamente un grafo? Según tengo entendido hay algoritmos para eso.
http://es.wikipedia.org/wiki/Ordenaci%C3%B3n_topol%C3%B3gica 2010/12/20 Andres Valloud <[email protected]> > A ver... supongan la siguiente jerarquia de clases: > > A1 > B1 > C1 > C2 > D1 > B2 > C3 > D2 > D3 > D4 > C4 > > Cuantas maneras hay de hacer un fileout de las definiciones de clase > de tal manera que se pueda hacer un file in en otra imagen? O sea, el > problema es que no se puede hacer un file out de C4 antes de B2 porque > si no cuando se hace file in de C4, su superclase B2 no existe. > > Es mas o menos facil encontrar una cota inferior. Haciendo breadth > first, hay 4 layers de clases con tamaños 1, 2, 4 y 4. Por lo tanto, > hay por lo menos 1! x 2! x 4! x 4! = 1152 maneras de hacer un file out > correctamente. Sin embargo, cuando busque exhaustivamente, encontre > 18900 ordenes diferentes. Pero bueno, 18900 es 2^2 * 3^3 * 5^2 * 7. > Entonces, pregunta... alguien sabe como calcular el numero de posibles > file outs sin tener que buscar exhaustivamente? Es mas o menos claro > que ese numero es el numero posible de traversals de un tree. Como se > calcula eso? Hay algun resultado ya hecho? > > Andres. > > -- > To post to this group, send email to [email protected] > To unsubscribe from this group, send email to > [email protected]<clubsmalltalk%[email protected]> > > http://www.clubSmalltalk.org -- To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] http://www.clubSmalltalk.org
