Que groso...
Locked
12
12
 
|
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 [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org |
|
|
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 <[hidden email]> A ver... supongan la siguiente jerarquia de clases: -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org |
|
|
¿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 <[hidden email]> escribió: Quizá estoy diciendo una obviedad, pero ¿eso no es ordenar topológicamente un grafo? -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org |
|
|
In reply to this post by Gaboto
Encontrar *un* orden que cumpla los requisitos es mas o menos facil.
El tema es que la solucion no es unica. Mi pregunta es cuantos ordenes posibles hay. 2010/12/20 Gaboto <[hidden email]>: > 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 <[hidden email]> >> >> 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 [hidden email] >> To unsubscribe from this group, send email to >> [hidden email] >> >> http://www.clubSmalltalk.org > > -- > To post to this group, send email to [hidden email] > To unsubscribe from this group, send email to > [hidden email] > > http://www.clubSmalltalk.org -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org |
|
|
In reply to this post by Andrés Macagno
Si, ese es un orden que funciona. Pero tambien "A1 B2 ... B1 ..."
funciona. Bueno, cuantos de esos hay? 2010/12/20 Andrés Macagno <[hidden email]>: > ¿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 <[hidden email]> 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 <[hidden email]> >>> >>> 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 [hidden email] >>> To unsubscribe from this group, send email to >>> [hidden email] >>> >>> http://www.clubSmalltalk.org >> >> -- >> To post to this group, send email to [hidden email] >> To unsubscribe from this group, send email to >> [hidden email] >> >> http://www.clubSmalltalk.org > > -- > To post to this group, send email to [hidden email] > To unsubscribe from this group, send email to > [hidden email] > > http://www.clubSmalltalk.org -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org |
|
|
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: [hidden email] [mailto:[hidden email]] En nombre de Andres Valloud Enviado el: Tuesday, December 21, 2010 12:03 AM Para: [hidden email] 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 <[hidden email]>: > ¿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 <[hidden email]> escribió: >> >> Quizá estoy diciendo una obviedad, pero ¿eso no es ordenar >> 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 <[hidden email]> >>> >>> 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 [hidden email] >>> To unsubscribe from this group, send email to >>> [hidden email] >>> >>> http://www.clubSmalltalk.org >> >> -- >> To post to this group, send email to [hidden email] >> To unsubscribe from this group, send email to >> [hidden email] >> >> http://www.clubSmalltalk.org > > -- > To post to this group, send email to [hidden email] > To unsubscribe from this group, send email to > [hidden email] > > http://www.clubSmalltalk.org -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org |
|
|
In reply to this post by Andres Valloud-5
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:[hidden email]] Enviado el: Tuesday, December 21, 2010 6:36 AM Para: '[hidden email]' 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: [hidden email] [mailto:[hidden email]] En nombre de Andres Valloud Enviado el: Tuesday, December 21, 2010 12:03 AM Para: [hidden email] 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 <[hidden email]>: > ¿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 <[hidden email]> escribió: >> >> Quizá estoy diciendo una obviedad, pero ¿eso no es ordenar >> 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 <[hidden email]> >>> >>> 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 [hidden email] >>> To unsubscribe from this group, send email to >>> [hidden email] >>> >>> http://www.clubSmalltalk.org >> >> -- >> To post to this group, send email to [hidden email] >> To unsubscribe from this group, send email to >> [hidden email] >> >> http://www.clubSmalltalk.org > > -- > To post to this group, send email to [hidden email] > To unsubscribe from this group, send email to > [hidden email] > > http://www.clubSmalltalk.org -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org |
|
|
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: [hidden email] [mailto:[hidden email]] En nombre de Angel "Java" Lopez Enviado el: Tuesday, December 21, 2010 6:57 AM Para: [hidden email] 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:[hidden email]] Enviado el: Tuesday, December 21, 2010 6:36 AM Para: '[hidden email]' 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: [hidden email] [mailto:[hidden email]] En nombre de Andres Valloud Enviado el: Tuesday, December 21, 2010 12:03 AM Para: [hidden email] 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 <[hidden email]>: > ¿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 <[hidden email]> escribió: >> >> Quizá estoy diciendo una obviedad, pero ¿eso no es ordenar >> 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 <[hidden email]> >>> >>> 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 [hidden email] >>> To unsubscribe from this group, send email to >>> [hidden email] >>> >>> http://www.clubSmalltalk.org >> >> -- >> To post to this group, send email to [hidden email] >> To unsubscribe from this group, send email to >> [hidden email] >> >> http://www.clubSmalltalk.org > > -- > To post to this group, send email to [hidden email] > To unsubscribe from this group, send email to > [hidden email] > > http://www.clubSmalltalk.org -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org |
|
|
Bueno, despues de la ducha, a ver si avanzo algo hacia la solución pedida:
N(A) = cantidad que resuelve el problema para A M(A) = cantidad de subclases de A, directas o no, incluyendo A B1,B2,... Bn subclases directas de A K(A) = (M(A)-1)! / M(B1)!M(B2)! ...M(Bn)! (vean que M(A)-1 = M(B1)+M(B2)+... M(Bn)) Es el numero de formas de resolver el problema, si las subclases de un nodo, siempre aparecieran en un orden: digamos que si B1 C2 D1 D2 C3 Siempre aparecería ..... B1.... C2.... D1...D2.... C3..... Donde los ... son clases de otras ramas "primas, hermanas, tias, etc" de B1. Hay, entonces, K(A) soluciones de esa forma. Sigue: N(A) = K(A) * N(B1) * N(B2) * ... N(Bn) Entonces, contempla que las subclases de B1 puedan aparecer ordenadas según N(B1) distintas formas, que son las formas de solucionar el problema para B1. Hmmm... se debería poder avanzar, expandiendo N(B1)*N(B2)... N(Bn) Deberia quedar todo expresado en sumas, multiplicaciones, factoriales de M(X), donde X recorre todos las clases. Algo como: N(A) = [(M(B1)+M(B2)+... +M(Bn))!/M(B1)!M(B2)!...M(Bn)!] [(M(C1)+M(C2)+...+M(Cm))!/M(C1)!M(C2)!...M(Cn)!] .... Recordando que si B1 tiene hijos directos C1, C2,... Cm, M(B1) = M(C1)+M(C2)+...M(Cm) + 1... vemos que en el denominador aparece M(B1)! Y en el numerador aparece (M(B1)-1)!... Con lo que queda, M(B1) en el denominador (notable! ;-) Sera entonces esto? N(A) = (M(A)-1)! / M(B1)M(B2).... M(Bn)M(C1)M(C2)...M(Cm)..... O, lo que es lo mismo N(A) = (M(B1)+M(B2)...+M(Bn))! / M(B1)M(B2).... M(Bn)M(C1)M(C2)...M(Cm)..... (el denominador es la multiplicacion de M(X) donde X pasea por cada clase) Jeje, espero en este cuarto mensaje, haber llegado mas cerca que los anteriores. Si la de arriba es al formula respuesta, debería poder deducirse de una forma mas fácil, un "aja!". Arriesgo: cada M(B1) del denominador dice: "de todas las formas que me da el numerador, tengo que quedarme con 1 de cada M(B1), que son las únicas donde B1 aparece antes que sus descendientes". Tengo que tomar el colectivo, debería haber comprobado todo esto con un calculo sobre un árbol en concreto... -----Mensaje original----- De: [hidden email] [mailto:[hidden email]] En nombre de Angel "Java" Lopez Enviado el: Tuesday, December 21, 2010 7:14 AM Para: [hidden email] Asunto: RE: [clubSmalltalk] Que groso... 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: [hidden email] [mailto:[hidden email]] En nombre de Angel "Java" Lopez Enviado el: Tuesday, December 21, 2010 6:57 AM Para: [hidden email] 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:[hidden email]] Enviado el: Tuesday, December 21, 2010 6:36 AM Para: '[hidden email]' 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: [hidden email] [mailto:[hidden email]] En nombre de Andres Valloud Enviado el: Tuesday, December 21, 2010 12:03 AM Para: [hidden email] 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 <[hidden email]>: > ¿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 <[hidden email]> escribió: >> >> Quizá estoy diciendo una obviedad, pero ¿eso no es ordenar >> 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 <[hidden email]> >>> >>> 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 [hidden email] >>> To unsubscribe from this group, send email to >>> [hidden email] >>> >>> http://www.clubSmalltalk.org >> >> -- >> To post to this group, send email to [hidden email] >> To unsubscribe from this group, send email to >> [hidden email] >> >> http://www.clubSmalltalk.org > > -- > To post to this group, send email to [hidden email] > To unsubscribe from this group, send email to > [hidden email] > > http://www.clubSmalltalk.org -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org |
|
|
In reply to this post by Gaboto
No es tan fácil como lo plantean. En pascal exsite el mismo problema: no se puede definir un procedimiento si este llama a otro que aun no esta definido. El problema es que si tengo 2 funciones recursivas que se llaman una a la otra, entones no puedo poner ninguna primero. La solución que se encontró en pascal fue hacer que las funciones tengan "forward" es decir, poner el nombre de la función con sus parámetros pero sin cuerpo, de modo que sirva para ser invocada (definir la segunda función) y posteriormente definir la primera. En smalltalk ocurre lo mismo por ejemplo la clase object tiene el método asString que retorna un string, tiene el método equals que retorna un booleano y el método hash que retorna un integer. De modo que se requiere tener una manera de cargar una clase que hace referencia a otra que aun no esta 100% definida. Si hiciéramos lo mismo en smalltalk pero con las clases, ?funcionaria? La ventaja en smalltalk es que puedes tener primero todas las definiciones de las clases y luego sus metodos, de modo que loque dije no es 100% necesario. Saludos, Guillermo Schwarz. -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org |
|
|
Que es lo que "No es tan facil como lo plantean"?
El problema que planteó Andrés habla de cargar clases de manera que siempre esté cargada la superclase que corresponda. El grafo de este tipo de dependencias es un arbol y como tal no tiene ciclos, entonces no existe el problema que vos planteas. Independientemente de eso, lo que pregunta andrés se podría traducir, en teoría de grafos, a calcular la cantidad de órdenes topológicos que tiene un árbol dado. 2010/12/21 Guillermo Schwarz <[hidden email]>
-- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org |
|
|
In reply to this post by Guillermo Schwarz
En este problema lo unico que me interesa son las definiciones de las
clases. Igual, para el problema general, no queda otra que crear una imagen a partir de codigo fuente. 2010/12/21 Guillermo Schwarz <[hidden email]>: > No es tan fácil como lo plantean. > En pascal exsite el mismo problema: no se puede definir un procedimiento si > este llama a otro que aun no esta definido. El problema es que si tengo 2 > funciones recursivas que se llaman una a la otra, entones no puedo poner > ninguna primero. La solución que se encontró en pascal fue hacer que las > funciones tengan "forward" es decir, poner el nombre de la función con sus > parámetros pero sin cuerpo, de modo que sirva para ser invocada (definir la > segunda función) y posteriormente definir la primera. > En smalltalk ocurre lo mismo por ejemplo la clase object tiene el método > asString que retorna un string, tiene el método equals que retorna un > booleano y el método hash que retorna un integer. De modo que se requiere > tener una manera de cargar una clase que hace referencia a otra que aun no > esta 100% definida. > Si hiciéramos lo mismo en smalltalk pero con las clases, ?funcionaria? > > La ventaja en smalltalk es que puedes tener primero todas las definiciones > de las clases y luego sus metodos, de modo que loque dije no es 100% > necesario. > Saludos, > Guillermo Schwarz. > El 20-12-2010, a las 22:35, Gaboto <[hidden email]> 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 <[hidden email]> >> >> 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 [hidden email] >> To unsubscribe from this group, send email to >> [hidden email] >> >> http://www.clubSmalltalk.org > > -- > To post to this group, send email to [hidden email] > To unsubscribe from this group, send email to > [hidden email] > > http://www.clubSmalltalk.org > > -- > To post to this group, send email to [hidden email] > To unsubscribe from this group, send email to > [hidden email] > > http://www.clubSmalltalk.org -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org |
|
|
In reply to this post by Gaboto
> Independientemente de eso, lo que pregunta andrés se podría traducir, en
> teoría de grafos, a calcular la cantidad de órdenes topológicos que tiene un > árbol dado. Si :). Andres. -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org |
|
|
In reply to this post by Angel "Java" Lopez
> No contemple que el problema admite que se "entrelacen".
Si, eso hace mas dificil el problema. Andres. -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org |
|
|
Hola gente!
Si, Andres, pero en mi ultimo mensaje se contemplo ese caso. Esa era la respuesta que buscabas? Supongo que conoces la solucion, la respuesta a tu problema. Nos leemos! Angel "Java" Lopez http://www.ajlopez.com http://twitter.com/ajlopez -----Original Message----- From: [hidden email] [mailto:[hidden email]] On Behalf Of Andres Valloud Sent: Tuesday, December 21, 2010 2:05 PM To: [hidden email] Subject: Re: [clubSmalltalk] Que groso... > No contemple que el problema admite que se "entrelacen". Si, eso hace mas dificil el problema. Andres. -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org |
|
|
Todavia tengo que leer tu ultimo mensaje :)... estoy en eso!
2010/12/21 Angel "Java" Lopez <[hidden email]>: > Hola gente! > > Si, Andres, pero en mi ultimo mensaje se contemplo ese caso. Esa era la > respuesta que buscabas? > > Supongo que conoces la solucion, la respuesta a tu problema. > > Nos leemos! > > Angel "Java" Lopez > http://www.ajlopez.com > http://twitter.com/ajlopez > > > -----Original Message----- > From: [hidden email] [mailto:[hidden email]] > On Behalf Of Andres Valloud > Sent: Tuesday, December 21, 2010 2:05 PM > To: [hidden email] > Subject: Re: [clubSmalltalk] Que groso... > >> No contemple que el problema admite que se "entrelacen". > > Si, eso hace mas dificil el problema. > > Andres. > > -- > To post to this group, send email to [hidden email] > To unsubscribe from this group, send email to > [hidden email] > > http://www.clubSmalltalk.org > > -- > To post to this group, send email to [hidden email] > To unsubscribe from this group, send email to [hidden email] > > http://www.clubSmalltalk.org -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org |
|
|
In reply to this post by Angel "Java" Lopez
> 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? Se minimiza con A1 B1 ... R1 y el resultado es 1. Claramente, hay solo una manera de hacer un fileout de la jerarquia de clases en la que cada clase tiene exactamente 1 subclase, salvo la ultima que tiene cero. Se maximiza con A1 B1 B2 ... B(r-1) y el resultado es (r-1)!. Este es el caso no-maximizable de ordenar r-1 cosas. O sea, no hay mas maneras posibles. Pero hay otras formas de arbol que llegan a (r-1)! maneras de hacer file out? Me parece que no. Considerese el caso de que haya r-2 ramas colgando de A1. Entonces alguna de esas ramas tiene que tener profundidad mayor que cero. Sea B1 esa rama. Eso quiere decir que N(B1) = 1 (porque hay r-2 ramas, asi que abajo de B1 hay C1 y nada mas). El resto de las ramas se pueden ordenar de (r-3)! maneras. Entre esas maneras, hay que intercalar dos. Eso se reduce a conseguir dos puntos de insercion, o sea el numero combinatorio \comb{(r-3)!}{2}, o sea (r-3)(r-4)/2. Pero (r-3)!(r-3)(r-4)/2 < (r-1)! porque (r-3)(r-4)/2 < (r-1)(r-2). No sera la super demostracion, pero me parece suficiente para creer que no hay otra manera de maximizar N(A1). Andres. -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org |
|
|
In reply to this post by Andres Valloud-5
El ùnico problema es que asumes que las clases no existen ya en la imagen a las que las vas a subir, y ese puede no ser el caso.
Creo que es màs inteligente asumir que existe un paquete que agrupa clases relacionadas y que està versionado. Al versionarlo sè que si subo el paquete XXX-v.2.0, debo primero eliminar el paquete XXX-v1.0.
Entonces puedes establecer dependencias entre paquetes junto con sus versiones. El caso que quieres resolver es sólo còmo guardar un paquete de manera que luego al leerlo las clases suban en el orden correcto, y creo que dado los requerimientos que hiciste, la respuesta es simplemente recorrer las clases del paquete, anotar las dependencias y guardar sòlo las clases:
1. Que no tienen dependencias. 2. Cuyas dependencias ya estàn guardadas. Una simplificaciòn equivalente del algoritmo anterior: 1. Guarda todas las clases del paquete en un set.
2. Saca una clase del set. Si la clase tiene dependencias, llama recursivamente a guardar su dependencia. 3. Guarda la clase en el archivo (file-out). 4. Cuando no hay màs clases en el set, termina.
5. Goto 2 Saludos, Guillermo.
-- 2010/12/20 Andres Valloud <[hidden email]> A ver... supongan la siguiente jerarquia de clases: -- Saludos cordiales, Guillermo Schwarz Sun Certified Enterprise Architect To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org |
|
|
Que tiene que ver que existan o no las clases con la cantidad de
maneras de hacer un fileout a priori cargable? 2010/12/21 Guillermo Schwarz <[hidden email]>: > El ùnico problema es que asumes que las clases no existen ya en la imagen a > las que las vas a subir, y ese puede no ser el caso. > Creo que es màs inteligente asumir que existe un paquete que agrupa clases > relacionadas y que està versionado. Al versionarlo sè que si subo el paquete > XXX-v.2.0, debo primero eliminar el paquete XXX-v1.0. > Entonces puedes establecer dependencias entre paquetes junto con sus > versiones. > El caso que quieres resolver es sólo còmo guardar un paquete de manera que > luego al leerlo las clases suban en el orden correcto, y creo que dado los > requerimientos que hiciste, la respuesta es simplemente recorrer las clases > del paquete, anotar las dependencias y guardar sòlo las clases: > 1. Que no tienen dependencias. > 2. Cuyas dependencias ya estàn guardadas. > Una simplificaciòn equivalente del algoritmo anterior: > 1. Guarda todas las clases del paquete en un set. > 2. Saca una clase del set. Si la clase tiene dependencias, llama > recursivamente a guardar su dependencia. > 3. Guarda la clase en el archivo (file-out). > 4. Cuando no hay màs clases en el set, termina. > 5. Goto 2 > Saludos, > Guillermo. > > 2010/12/20 Andres Valloud <[hidden email]> >> >> 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 [hidden email] >> To unsubscribe from this group, send email to >> [hidden email] >> >> http://www.clubSmalltalk.org > > > -- > Saludos cordiales, > > Guillermo Schwarz > Sun Certified Enterprise Architect > > -- > To post to this group, send email to [hidden email] > To unsubscribe from this group, send email to > [hidden email] > > http://www.clubSmalltalk.org -- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org |
|
|
In reply to this post by Andres Valloud-5
Si, termina siendo
N(A) = M(A)! / M(A)M(B1)M(B2)....M(C1)M(C2) ...... donde M(X) es la cantidad de nodos del arbol que nace en X, incluyendo X. Los casos extremos son: M(B1)=M(B2)=....=M(Bn)=1 dando N(A) = M(A)!/M(A) = (M(A)-1)! y M(A)=M(B1)+1 M(B1)=M(C1)+1 ... dando N(A) = M(A)! / M(A)! = 1 2010/12/21 Andres Valloud <[hidden email]>
-- To post to this group, send email to [hidden email] To unsubscribe from this group, send email to [hidden email] http://www.clubSmalltalk.org |
«
Return to Español (Spanish)
|
1 view|%1 views
| Free forum by Nabble | Edit this page |