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
