[Programación] Re: [Programación] Re: =?iso-8
859-1?q?=5BProgramaci=F3n=5D_Ge
nerar_cartones_de_Bingo_--_una
?= =?iso-8859-1?q?_soluci=F3n?=
Rafael Bidegain
programacion@lugro.org.ar
Wed, 16 Mar 2005 08:14:38 -0300
Federico
es muy interesante tu solucion, yo si le voy a dedicar tiempo a la
optimizacion del algoritmo.
me lo podes enviar?
si te resulta mas comodo subilo a algun sitio por si hay otros interesados.
muchas gracias.
On Wed, 16 Mar 2005 03:12:37 -0300, Federico Wiecko <fedewi@mail15.com> wrote:
> Bueno, una solución mala pero que funciona es el siguiente código Haskell.
>
> -------------------------------------------------------------------------------------------------------
> -- Obtiene todas las combinaciones de n tomadas de a m
> combinaciones:: Int->Int->[[Int]]
> combinaciones n m | n < m = error "no se puede tomar mas de lo que
> se tiene"
> | n == m = [[1..n]]
> | m == 0 = [[]]
> | otherwise = (combinaciones (n-1) m) ++ map (flip
> (++) [n]) (combinaciones (n-1) (m-1))
>
> -- Devuelve True si ningun elemento de xs pertenece a ys
> ncontains:: [Int]->[Int]->Bool
> ncontains xs [] = True
> ncontains [] ys = True
> ncontains (x:xs) ys | and(map (flip (/=) x) ys) = ncontains xs ys
> | otherwise = False
>
> -- Devuelve una plancha valida
> plancha:: [Int]->[[Int]]->[[Int]]-> [[Int]]-> ([[Int]],[[Int]])
>
> plancha xs [] [] resto = ([], resto++[xs])
> plancha xs [] (zs:zss) resto | length zss==2 = ((zs:zss), resto)
> | length zss>2 = plancha zs zss [zs] resto
> | otherwise = error "La pucha che!"
> plancha xs (ys:yss) zss resto | ncontains xs ys = plancha xs yss (ys:zss)
> resto
> | otherwise = plancha xs yss zss
> (ys:resto)
>
> -- Obtiene todas las planchas posibles
> planchas:: ([[[Int]]],[[Int]])->[[[Int]]]
> planchas (xsss, []) = xsss
> planchas (xsss,(ys:yss)) | length xsss >10 = xsss
> | otherwise = planchas ((\(x,y) ->
> ((ys:x):xsss, y)) (plancha ys yss [] []))
>
> -- Obtiene la lista de a 4 planchas a partir de las combinaciones de 20
> tomadas de a 5
> final:: [[[Int]]]
> final= planchas([], combinaciones 20 5)
>
> --------------------------------------------------------------------------------------------------------
> Con mi maquina, un AMD XP 2000 tarde 50 seg. en obtener solo 10 cartones.
>
> [[[2,5,6,7,8],[1,12,13,18,19],[9,11,15,17,20],[3,4,10,14,16]],
> [[1,12,13,15,18],[3,4,9,11,19],[2,5,10,14,20],[6,7,8,16,17]],[[2,3,4,9,11],
> [10,14,16,17,20],[1,5,6,15,18],[7,8,12,13,19]],[[10,14,16,17,18],
> [5,6,7,8,20],[9,12,13,15,19],[1,2,3,4,11]],[[5,6,7,8,9],[1,12,13,15,19],
> [2,3,11,14,16],[4,10,17,18,20]],[[1,12,13,14,19],[2,3,4,11,15],
> [6,10,17,18,20],[5,7,8,9,16]],[[2,3,4,6,11],[10,16,17,18,20],[5,7,8,9,19],
> [1,12,13,14,15]],[[10,16,17,18,19],[5,7,8,9,20],[6,11,13,14,15],
> [1,2,3,4,12]],[[5,7,8,9,11],[6,12,13,14,15],[1,2,3,10,16],[4,17,18,19,20]],
> [[10,12,13,14,15],[1,2,3,4,6],[5,17,18,19,20],[7,8,9,11,16]],[[1,2,3,4,5],
> [16,17,18,19,20],[11,12,13,14,15],[6,7,8,9,10]]]
>
> Seguramente se puede optimizar pero no voy a perder el tiempo.
> ------------------------------------------------------------------------------------------------
> Les cuento la idea del algoritmo:
>
> 1) inicialmente se obtienen las tuplas de 5 elementos producto de la C(20,5)
> 2) para el primer cartón se separan los cartones en dos conjuntos:
> a) los que tienen al menos 1 nro en comun
> b) los que no tienen ninguno
> 3) se toma el conjunto b) y se repite el procedimiento anterior
> Si se obtienen 3 cartones con números diferentes entre si y agregandole
> el primer carton se obtiene una plancha de a 4. Los números sobrantes se
> agregan al conjunto a)
> Pero si se llego al final de la lista y no se obtuvieron 3 cartones, se
> toman los cartones del conjunto b) y se los agrega al final del conjunto a)
> Este caso es el mismo que enuncie ayer en un mail=
> supongamos ya tener un carton asi
> [[1,2,3,4,5],[6,7,8,9,10],[11,12,13,14,15],[16,17,18,19,20]]
>
> y ahora empezando con
> [2,3,4,5,6]
> podríamos obtener
> [1,7,8,9,11],[10,12,13,14,15] y llegar al final de nuestra lista
> sin encontrar el que necesitamos (que es [16,17,18,19,20] que ya esta en uso)
> En este caso, los cartones [1,7,8,9,11],[10,12,13,14,15] se mandan
> al final de la lista y se continua con la busqueda
>
> 4) se repite el punto 2) pasando ahora el siguiente elemento de la lista
> --------------------------------------------------------------------------------------------------
>
> Cabe aclarar que para 100 cartones el tiempo fue de 5' 30'', ya que el
> espacio de busqueda decrece a medida que se obtienen mas cartones
>
> Bastante ineficiente .. pero funcionando.
>
> Espero encuentren mejores soluciones.
>
> Slds.
> Federico .-
>
> On Wednesday 16 March 2005 00:20, Pablito wrote:
> > Gente:
> > Me quede pensando el problema. Me parece muy interesante. Porque es
> > fácil de entender, parece simple de resolver, pero no lo es. Me hace
> > acordar al problema del circuito hamiltoniano. Esta bueno intentar
> > resolver el problema por cuenta propia, pero si nuestra solución es
> > aparentemente ineficiente, no nos con vence o tal vez no la tenemos, es
> > mejor pedir ayuda. Las personas apropiadas para resolver este problema
> > son los matemáticos. No traté de ofender a nadie con lo que dije en el
> > mail anterior.
> >
> > Rafael:
> > Al problema lo intenté pensar de varias maneras buscando una solucion,
> > pero sin tener exito, les paso a comentar un enfoque, a ver si a alguien
> > se le prende la lamparita.
> >
> > Supongan que tienen generados todos los cartones. Es más supongan que
> > tienen un grafo, en donde los vértices son los cartones, y dos vertices
> > se unen si no tienen ninguna cifra en común.
> > Por lo tanto tengo un grafo de C(20 5)=15504 vertices donde cada uno se
> > une con C(15 5)=3003 vertices.
> > Cada solución posible del problema se puede ver como un "coloreo" de
> > grupo de 4 vertices que se unen todos con todos entre ellos (un completo
> > de 4). (¿se entiende?)
> >
> > Para entenderlo mejor se pueden construir un super-mini-bingo. Supongan
> > que los cartones tienen solo 2 números y los numeros van del 1 al 6.
> > (entonces C(6 2)=15 vertices). Y los cartones se agrupan de a 3. (Cada
> > vertice tiene C(4 2)=6 aristas).
> >
> > En este caso hay que pintar con colores diferentes triangulos (un
> > completo de 3).
> >
> > Creo que el mini-modelo es bueno ya que se cumple lo siguiente:
> >
> > agrupacion de cartones*cantidad de numeros por carton= cantidad de
> > numeros posibles.
> >
> > en el Bingo:
> >
> > 4*5=20.
> >
> > en el mini-modelo:
> >
> > 2*3=6.
> >
> > Por ahi alguien conoce algún algoritmo para hacer este coloreo.
> >
> > Qué les parece si proponemos una manera (así sea fuerza bruta) y la
> > tratamos de mejorar. Tal vez lleguemos a alguna euristica simpática.
> >
> > Saludos.
> > Pablito.
> >
> >
> >
> >
> >
> >
> > _______________________________________________
> > Programacion mailing list
> > Programacion@lugro.org.ar
> > http://www.lugro.org.ar/mailman/listinfo/programacion
>
> _______________________________________________
> Programacion mailing list
> Programacion@lugro.org.ar
> http://www.lugro.org.ar/mailman/listinfo/programacion
>
--
/* Rafael Bidegain
Linux Registered User # 204304
CaFeLUG Grupo de Usuarios de Software Libre de Capital Federal
http://www.cafelug.org.ar */