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]<clubsmalltalk%[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]<clubsmalltalk%[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]<clubsmalltalk%[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]<clubsmalltalk%[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]<clubsmalltalk%[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]<clubsmalltalk%[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]<clubsmalltalk%[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]<clubsmalltalk%[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
