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
