Menu Close

Sucesiones de listas de números

En la Olimpiada Internacional de Matemáticas del 2012 se propuso el siguiente problema:

Varios enteros positivos se escriben en una lista. Iterativamente, Alicia elige dos números adyacentes x e y tales que x > y y x está a la izquierda de y y reemplaza el par (x,y) por (y+1,x) o (x-1,x). Demostrar que sólo puede aplicar un número finito de dichas iteraciones.

Por ejemplo, las transformadas de la lista [1,3,2] son [1,2,3] y [1,3,3] y las dos obtenidas son finales (es decir, no se les puede aplicar ninguna transformación).

Definir las funciones

   soluciones :: [Int] -> [Estado]
   finales :: [Int] -> [[Int]]
   finalesMaximales :: [Int] -> (Int,[[Int]])

tales que

  • (soluciones xs) es la lista de pares (n,ys) tales que ys es una lista final obtenida aplicándole n transformaciones a xs. Por ejemplo,
     λ> soluciones [1,3,2]
     [(1,[1,3,3]),(1,[1,2,3])]
     λ> sort (nub (soluciones [3,3,2]))
     [(1,[3,3,3]),(2,[2,3,3]),(2,[3,3,3])]
     λ> sort (nub (soluciones [3,2,1]))
     [(2,[2,2,3]),(3,[2,2,3]),(3,[2,3,3]),(3,[3,3,3]),(4,[2,3,3]),(4,[3,3,3])]
  • (finales xs) son las listas obtenidas transformando xs y a las que no se les puede aplicar más transformaciones. Por ejemplo,
     finales [1,2,3]               ==  [[1,2,3]]
     finales [1,3,2]               ==  [[1,2,3],[1,3,3]]
     finales [3,2,1]               ==  [[2,2,3],[2,3,3],[3,3,3]]
     finales [1,3,2,4]             ==  [[1,2,3,4],[1,3,3,4]]
     finales [1,3,2,3]             ==  [[1,2,3,3],[1,3,3,3]]
     length (finales [9,6,0,7,2])  ==  19
     length (finales [80,60..0])   ==  420
  • (finalesMaximales xs) es el par (n,yss) tal que la longitud de las cadenas más largas de transformaciones a partir de xs e yss es la lista de los estados finales a partir de xs con n transformaciones. Por ejemplo,
     finalesMaximales [9,5,7]   ==  (2,[[6,8,9],[8,8,9]])
     finalesMaximales [3,2,1]   ==  (4,[[2,3,3],[3,3,3]])
     finalesMaximales [3,2..0]  ==  (10,[[2,3,3,3],[3,3,3,3]])
     finalesMaximales [4,3..0]  ==  (20,[[3,4,4,4,4],[4,4,4,4,4]])

Soluciones

import Data.List (nub, sort)
import I1M.BusquedaEnEspaciosDeEstados (buscaEE)
 
type Estado = (Int,[Int])
 
inicial :: [Int] -> Estado
inicial xs = (0,xs)
 
esFinal :: Estado -> Bool
esFinal e = null (sucesores e)
 
--    λ> sucesores [9,6,0,7,2]
--    [[7,9,0,7,2],[8,9,0,7,2],[9,1,6,7,2],[9,5,6,7,2],[9,6,0,3,7],[9,6,0,6,7]]
sucesores :: Estado -> [Estado]
sucesores (_,[])  = []
sucesores (_,[_]) = []
sucesores (n,x:y:xs)
  | x > y     = [(n+1,y+1:x:xs), (n+1,x-1:x:xs)] ++ yss
  | otherwise = yss
  where yss = [(m,x:ys) | (m,ys) <- sucesores (n,y:xs)]
 
soluciones :: [Int] -> [Estado]
soluciones xs =
  buscaEE sucesores esFinal (inicial xs)
 
finales :: [Int] -> [[Int]]
finales xs =
  sort (nub (map snd (soluciones xs)))
 
finalesMaximales :: [Int] -> (Int,[[Int]])
finalesMaximales xs =
  (m, [xs | (n,xs) <- es, n == m])
  where es    = sort (nub (soluciones xs))
        (m,_) = maximum es
Ejercicio

3 soluciones de “Sucesiones de listas de números

  1. frahidzam
    type Estado = (Int,[Int])
    soluciones :: [Int] -> [Estado]
    soluciones xs = buscaEE (sucesoresN) (esFinal) (0,xs)
      where
    esFinal (_,xs) = and [x <= y | (x,y) <- zip xs (tail xs)]
     
    sucesoresN (n,xs) = [(n+1,ys) | ys <- transformadas [] (zip xs (tail xs)) []]
     
    transformadas :: [(Int,Int)] -> [(Int,Int)] -> [[Int]] -> [[Int]]
    transformadas _ [] xss = xss
    transformadas ys ((a,b):xs) xss | a > b = transformadas (ys ++ [(a,b)]) xs ([uneD (uneI ys  (b+1,a))  xs]) ++ ([uneD (uneI ys  (a-1,a))  xs]) ++ xss 
                                            | otherwise = transformadas (ys ++ [(a,b)]) xs xss
     
    uneI :: [(Int,Int)] -> (Int,Int) -> [Int]
    uneI xs (a,b) | null xs = [a,b]
                  | otherwise = init (transforma xs) ++ [a,b]
     
    uneD :: [Int] -> [(Int,Int)] -> [Int]
    uneD xs ys | null ys = xs
               | otherwise =  xs ++ (tail (transforma ys))
     
     
    transforma [(a,b)] = [a,b]
    transforma ((a,b):xs) = a:transforma xs
    transforma [] = []
     
    finales :: [Int] -> [[Int]]
    finales xs = sort $ nub [ys | (n,ys) <- bs]
     where bs = soluciones xs
     
    finalesMaximales :: [Int] -> (Int,[[Int]])
    finalesMaximales xs = (n,[ys | (a,ys) <- bs, a == n])
      where  bs = sort $ nub $ soluciones xs
             n = maximum (map fst bs)
  2. adogargon
    import Data.List
    type Estado = (Int,[Int])
     
    sucesoresL :: [Int] -> [[Int]]
    sucesoresL [] = []
    sucesoresL [x] = [[x]]
    sucesoresL (x:y:xs) | x > y =((y+1):x:xs):(x-1:x:xs):(map (x:) (sucesoresL (y:xs)))
                        | otherwise = map (x:) (sucesoresL (y:xs))
     
    sucesoresE :: Estado -> [Estado]
    sucesoresE (n,xs) = [(n+1,ys) | ys <-(delete xs (sucesoresL xs))]
     
    esFinal :: Estado -> Bool
    esFinal (n,xs) = xs == sort xs
     
    soluciones :: [Int] -> [Estado]
    soluciones xs = buscaEE sucesoresE esFinal (0,xs)
     
    finales :: [Int] -> [[Int]]
    finales = nub . map snd . soluciones 
     
    finalesMaximales :: [Int] -> (Int,[[Int]])
    finalesMaximales = foldl1 f . map g . last . groupBy p . sort . soluciones
      where f (a,xss) (b,yss) = (a,nub (xss++yss))
            g (a,xs) = (a,[xs])
            p (a,xs) (b,ys) = a == b
  3. luipromor
    soluciones :: [Int] -> [(Int,[Int])]
    soluciones xs = buscaEE sucesiones esFinal ( (0,xs))
      where esFinal (_,xs) =  not $ or [ f x xs | x <- xs]        
            sucesiones (n,xs) =  [ (n+1, aux x xs h) | h <- [0,1] , x <- xs , f x xs]        
            aux a (x:y:xs)  0  | x == a && a >y  = (y+1):x:xs
                               | otherwise = x : aux a (y:xs) 0
            aux a (x:y:xs)  1  | x == a && a > y = (x-1):x:xs
                               | otherwise = x : aux a (y:xs) 1
            f a (x:y:xs) | a == x = x > y || f a (y:xs)
                         | otherwise = f a (y:xs)
            f _ [_] = False
     
    finales :: [Int] -> [[Int]]
    finales = nub.map snd.soluciones
     
    finalesMaximales :: [Int] -> (Int,[[Int]])
    finalesMaximales xs = (y,[ ys | (x,ys) <- ys , x == y ])
      where ys = nub $  soluciones xs
            y = maximum $ map fst $ ys

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.