Menu Close

Mayor número obtenido intercambiando dos dígitos

Definir la función

   maximoIntercambio :: Int -> Int

tal que (maximoIntercambio x) es el máximo número que se puede obtener intercambiando dos dígitos de x. Por ejemplo,

   maximoIntercambio 983562  ==  986532
   maximoIntercambio 31524   ==  51324
   maximoIntercambio 897     ==  987

Soluciones

import Data.Array
 
-- 1ª solución
-- ===========
 
maximoIntercambio :: Int -> Int
maximoIntercambio = maximum . intercambios
 
-- (intercambios x) es la lista de los números obtenidos intercambiando
-- dos dígitos de x. Por ejemplo,
--    intercambios 1234  ==  [2134,3214,4231,1324,1432,1243]
intercambios :: Int -> [Int]
intercambios x = [intercambio i j x | i <- [0..n-2], j <- [i+1..n-1]]
    where n = length (show x)
 
-- (intercambio i j x) es el número obtenido intercambiando las cifras
-- que ocupan las posiciones i y j (empezando a contar en cero) del
-- número x. Por ejemplo,
--    intercambio 2 5 123456789  ==  126453789
intercambio :: Int -> Int -> Int -> Int
intercambio i j x = read (concat [as,[d],cs,[b],ds])
    where xs        = show x
          (as,b:bs) = splitAt i xs 
          (cs,d:ds) = splitAt (j-i-1) bs
 
-- 2ª solución (con vectores)
-- ==========================
 
maximoIntercambio2 :: Int -> Int
maximoIntercambio2 = read . elems . maximum . intercambios2
 
-- (intercambios2 x) es la lista de los vectores obtenidos
-- intercambiando dos elementos del vector de dígitos de x. Por ejemplo, 
--    ghci> intercambios2 1234
--    [array (0,3) [(0,'2'),(1,'1'),(2,'3'),(3,'4')],
--     array (0,3) [(0,'3'),(1,'2'),(2,'1'),(3,'4')],
--     array (0,3) [(0,'4'),(1,'2'),(2,'3'),(3,'1')],
--     array (0,3) [(0,'1'),(1,'3'),(2,'2'),(3,'4')],
--     array (0,3) [(0,'1'),(1,'4'),(2,'3'),(3,'2')],
--     array (0,3) [(0,'1'),(1,'2'),(2,'4'),(3,'3')]]
intercambios2 :: Int -> [Array Int Char]
intercambios2 x = [intercambioV i j v | i <- [0..n-2], j <- [i+1..n-1]]
    where xs = show x
          n  = length xs
          v  = listArray (0,n-1) xs
 
-- (intercambioV i j v) es el vector obtenido intercambiando los
-- elementos de v que ocupan las posiciones i y j. Por ejemplo,
--    ghci> intercambioV 2 4 (listArray (0,4) [3..8])
--    array (0,4) [(0,3),(1,4),(2,7),(3,6),(4,5)]
intercambioV :: Int -> Int -> Array Int a -> Array Int a
intercambioV i j v = v // [(i,v!j),(j,v!i)]
Medio

7 soluciones de “Mayor número obtenido intercambiando dos dígitos

  1. alerodrod5
     
    maximoIntercambio :: Int -> Int
    maximoIntercambio x = numero (aux x)
      where aux x | n == maximum xs = n : aux (numero ys)
                  | otherwise = cambia m  n  xs
                    where m = maximum xs
                          n = head xs
                          xs = [read [d] | d<-show x]
                          ys = tail xs
    cambia _ _ [] = []
    cambia a  b (x:xs) | b == x = a : reverse(cambia b a (reverse xs)) 
                       | otherwise = x:cambia a b xs
    numero xs =sum [x*10^n | (x,n) <- zip xs [length xs -1, length xs-2..0]]
      • alerodrod5

        Esta creo que si es correcta, solucionando el problema con los ceros intermedios

        maximoIntercambio :: Int -> Int
        maximoIntercambio x = numero (aux xs)
          where  xs = [read [d] | d<-show x]
                 aux xs | n == maximum xs = n : aux  ys
                       | otherwise = cambia m  n  xs
         
                        where m = maximum xs
                              n = head xs
                              ys = tail xs
        cambia _ _ [] = []
        cambia a  b (x:xs) | b == x = a : reverse(cambia b a (reverse xs)) 
                           | otherwise = x : cambia a b xs
        numero xs = sum [x*10^n | (x,n) <- zip xs [length xs -1, length xs-2..0]]
        • jaibengue
          -- λ> maximoIntercambio 99955421
          -- *** Exception: Prelude.head: empty list
           
          -- λ> maximoIntercambio 8522
          -- *** Exception: Prelude.head: empty list
           
          -- En lugar de: --
           
          -- λ> maximoIntercambio 99955421
          -- 99955412
           
          -- λ> maximoIntercambio 8522
          -- 8522
  2. angruicam1
    maximoIntercambio :: Int -> Int
    maximoIntercambio x = read (busc (show x))
      where camb m z (y:ys)
              | y == m    = z : ys
              | otherwise = y : camb m z ys
            busc xs@(y:ys)
              | y == m    = y : busc ys
              | otherwise = m : (reverse (camb m y (reverse ys)))
              where m = maximum xs
            busc _ = []
  3. jaibengue

    Una función lineal en el número de dígitos de n:

    import Data.Array
    import Data.List
     
    maximoIntercambio :: Integer -> Integer
    maximoIntercambio n = read (swap s (getInd ls ls))
      where ls = arrTlist (listRarr (zip s [0..]) ini)
            ini = (array ('0','9') [(i,(-1,-1))|i<-['0'..'9']])
            s = show n
     
    listRarr :: Ord a => Ix a => [(a,Int)] -> Array a (Int,Int) -> Array a (Int,Int)
    listRarr ((x,i):xs) arr = listRarr xs (arr//[(x, (f,i))])
      where (f1,_) = (arr!x)
            f | f1 == (-1) = i
              | otherwise  = f1
    listRarr _ arr = arr
     
    arrTlist :: Ord a => Ix a => Array a (Int,Int) -> [(a,(Int,Int))]
    arrTlist = filter ((_,(e,_)) -> e/=(-1)).sortBy ((_,(e1,_)) (_,(e1',_)) -> compare e1 e1').assocs
     
    getInd :: Ord a => [(a,(Int,Int))] -> [(a,(Int,Int))] -> (Int,Int)
    getInd ((i,(e1,e2)):xs) ys | aux == [] = getInd xs ys
                               | otherwise = (e1, (snd.snd.maximum) aux)
      where aux         = filter f ys
            f (a,(_,s)) = a > i && s > e1
    getInd [] ys = (aux-1,aux)
      where aux = maximum (map ((i,(e1,e2)) -> e2) ys)
     
    swap :: Ord a => [a] -> (Int,Int) -> [a] 
    swap xs (i,j)   = take i xs ++ [xs!!j] ++ take (j-i-1) (drop (i+1) xs) ++ [xs!!i] ++ drop (j+1) xs
  4. Maria Ruiz
     
    import Data.List
     
    digitos :: Int -> [Int]
    digitos n = [read [x] | x <- show n]
     
    numero :: [Int] -> Int
    numero ds = read (concatMap show ds)
     
    maximoIntercambio :: Int -> Int
    maximoIntercambio n | xs == ds  = intercambiaF n
                        | otherwise = numero (inter d x ds)
      where ds = digitos n
            xs = sortBy (flip compare) ds
            (d,x) = head [(d,x) | (d,x) <- zip ds xs, d < x]
     
    -- (intercambiaF n) intercambia los dos últimos dígitos de un número
    intercambiaF n = q*100 + 10*b + a
      where (q,r) = quotRem n 100
            (a,b) = quotRem r 10
     
    -- (inter d y xs) intercambia d con y en xs, siendo d < y.
    inter d y xs = as ++ y:ds ++ d:tail es
      where (as, bs) = span (>y) xs
            (ds,es) = span (/=y) (tail bs)

Escribe tu solución

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