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
