Listo, escrito esta. 2010/12/21 Angel Java Lopez <[email protected]>: > Yes! > > Y ahi me di cuenta del "aja", que explique en mi email post-ducha... Lo que > hace el agua caliente ;-) > > Cada factor M(X) del denominador "descarta" secuencias erroneas, donde X no > aparece primero en la secuencia insertada en la secuencia total: > > .... X ...... X?...X?.... X?...X?.... > > donde los X? son los descendientes directos o no de X. > > Nos leemos! > > Angel "Java" Lopez > http://www.ajlopez.com > http://twitter.com/ajlopez > > > 2010/12/21 Andres Valloud <[email protected]> >> >> Ah, un detalle... se terminan cancelando todos los terminos porque >> eventualmente, al descender por el arbol lo suficiente, M(X) = 1 y >> luego N(X)=1 con lo que los terminos eventualmente desaparecen. >> >> 2010/12/21 Andres Valloud <[email protected]>: >> > A ver si entendi bien. Con tu notacion, lo que decis es lo siguiente. >> > >> > 1. Existe por lo menos una manera de resolver este problema. Por >> > ejemplo, breadth first. Sea K ese orden. Es claro que en ese orden, >> > como es valido, la subsecuencia de cada Bi va a estar bien ordenada. >> > Hay M(Bi)! maneras de ordenar cada una de estas subsecuencias, pero en >> > K ese orden esta fijo. La pregunta entonces es cuantos ordenes K hay >> > donde los ordenes de cada subsecuencia para cada Bi es fijo. >> > >> > Claramente hay M(A-1)! ordenes, ya que A siempre tiene que aparecer >> > primero en cualquier orden. De todos estos, las clases >> > correspondientes a cada rama Bi siempre aparecen en el mismo orden >> > porque dijimos que en K el orden es fijo. Por lo tanto, al fijar el >> > orden Bi, hay que dividir a M(A-1)! por M(Bi)!. Luego, la cantidad de >> > ordenes K que empiezan en A es >> > >> > K(A) = M(A-1)! / M(B1)!M(B2)!...M(Bb)! >> > >> > donde B1...Bb son las subclases directas de A. >> > >> > 2. Ahora bien, K(A) mide la cantidad de ordenes posibles dado un >> > orden fijo para cada rama Bi. Es claro que N(A) entonces debe ser >> > K(A) multiplicado por cada cantidad de maneras posibles de resolver >> > cada rama Bi. Luego, >> > >> > N(A) = K(A) * N(B1) * N(B2) * ... * N(Bb) >> > >> > No puede haber duplicados en esta lista, ya que en cada uno de estos >> > ordenes existe por lo menos una subsecuencia para alguna rama Bi que >> > es diferente. >> > >> > Ahora bien, reemplazando N(B1) por K(B1) * N(C1) * N(C2) * ... * >> > N(Cc), obtenemos >> > >> > N(A) = K(A) * K(B1) * N(C1) * ... * N(Cc) * N(B2) * ... * N(Bb) >> > >> > Pero K(A) = M(A-1)! / M(B1)!M(B2)!...M(Bb)!, y K(B1) = M(B1-1)! / >> > (M(C1)! * ... * M(Cc)!). De aqui se simplifica M(B1-1)! / M(B1)! = 1 >> > / M(B1), y queda >> > >> > N(A) = M(A-1)! / M(B1) * (N(C1) * ... * N(Cc)) / (M(C1)! * ... * >> > M(Cc)!) * (N(B2) * ... * N(Bb)) >> > >> > Reemplazando N(C1) por K(C1) * N(D1) * ... * N(Dd), obtenemos M(C1) en >> > el denominador. Siguiendo de este modo se cancelan casi todos los >> > terminos excepto >> > >> > N(A) = M(A-1)! / (\prod_X M(X)) >> > >> > Si? >> > >> > Andres. >> > >> > 2010/12/21 Angel "Java" Lopez <[email protected]>: >> >> 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: [email protected] >> >> [mailto:[email protected]] >> >> En nombre de Angel "Java" Lopez >> >> Enviado el: Tuesday, December 21, 2010 7:14 AM >> >> Para: [email protected] >> >> 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: [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 >> >> >> >> -- >> >> 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
