Que risa ver lo que pasa en el caso donde N(A) se minimiza...
A1
B1
C1
...
R1
Te queda
N(A1) = M(A1-1)! / M(B1)!M(C1)!...M(R1)!
o sea
N(A1) = (R-1)! / (R-1)(R-2)...(2)(1) = 1
2010/12/21 Andres Valloud <[email protected]>:
> Che pensando un poco en esto, voy a ver de escribirlo con otra
> notacion que tenga mas que ver con composicion de funciones. Por
> ejemplo,
>
> G(A,1) = B1
> G(G(A, 1), 2) = C2
>
> Y asi. La idea es que G^n(A, ...) es una hoja, y M(hoja)=1.
>
> 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
