[Programación] Re: [Programación] Generar cartones de Bingo -- una
solución
Federico Wiecko
programacion@lugro.org.ar
Wed, 16 Mar 2005 03:12:37 -0300
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