Argg!! Sigo contando mal N(A) seria 2! N(B1) * N(B2) Si las clases de B1 vinieran todas primero que las de B2, o al revés. No contemple que el problema admite que se "entrelacen".
Los dejo tranquilos por un rato.. ;-) Si tuviera que "arriesgar" una formula ahora, seria: N(A) = (N(B1)+N(B2)+...)! / N(B1)! N(B2)! ... Ya va apareciendo Pascal por aca... Interesante problema, Andres! -----Mensaje original----- De: [email protected] [mailto:[email protected]] En nombre de Angel "Java" Lopez Enviado el: Tuesday, December 21, 2010 6:57 AM Para: [email protected] Asunto: RE: [clubSmalltalk] Que groso... Disculpen, esta mal contado, no es N(A) = n! (N(B1) + N(B2) + ... + N(Bn)) Sino N(A) = n! (N(B1) * N(B2) * ... * N(Bn)) Cada clase con, digamos, k descendientes directos, aporta un factor k! a N(A), no importa el nivel en el que este. Las clases sin descendientes, aportan un factor 0! = 1, podemos poner. N(A) = la multiplicación de los j!, donde j es la cantidad de descendientes directos de cada clase, incluyendo A Ahora si? ;-) Dado un árbol de clases con raíz A, con cantidad de nodos r, cual es la forma del nodo para maximizar N(A)? Y para minimizarlo? -----Mensaje original----- De: Angel "Java" Lopez [mailto:[email protected]] Enviado el: Tuesday, December 21, 2010 6:36 AM Para: '[email protected]' Asunto: RE: [clubSmalltalk] Que groso... Hola gente! A ver si entendi... Sea N(A1) el numero de maneras de resolver el problema para A1 y sus descendientes. Sera: N(A1) = 2! (N(B1) + N(B2)) En general, N(A) = n! (N(B1) + N(B2) + ... + N(Bn)) Donde n es la cantidad de descendientes directos de A. N(X) = 1 si X no tiene descendientes. Ahora, es cuestión de hacer las cuentas... ;-) Habre contado bien? Si a partir de A, siempre tenemos que cada clase tiene n descendientes directos (n fijo) hasta el nivel m, queda N(A) = (n*n!)^m Nos leemos! Angel "Java" Lopez http://www.ajlopez.com http://twitter.com/ajlopez -----Mensaje original----- De: [email protected] [mailto:[email protected]] En nombre de Andres Valloud Enviado el: Tuesday, December 21, 2010 12:03 AM Para: [email protected] Asunto: Re: [clubSmalltalk] Que groso... Si, ese es un orden que funciona. Pero tambien "A1 B2 ... B1 ..." funciona. Bueno, cuantos de esos hay? 2010/12/20 Andrés Macagno <[email protected]>: > ¿En orden no funciona? Es decir, empezando por A1 y finalizando con C4. > > A1 B1 C1 C2 D1 B2 C3 D2 D3 D4 C4 > > Se que no responde a tu pregunta, pero bueno ;-) > > Saludos. > > El 20 de diciembre de 2010 22:35, Gaboto <[email protected]> escribió: >> >> 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] >>> >>> 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 > > -- > To post to this group, send email to [email protected] > To unsubscribe from this group, send email to > [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 -- To post to this group, send email to [email protected] To unsubscribe from this group, send email to [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
