Menu Close

Mayor número obtenido intercambiando dos dígitos

José A. Alonso,

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. Responder
    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]]
      • Responder
        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]]
        • Responder
          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. Responder
    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. Responder
    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. Responder
    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.