Mayor número obtenido intercambiando dos dígitos

PorJosé A. Alonso 3-abril-201810-abril-2018

Definir la función

   maximoIntercambio :: Int -> Int

1	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

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)]

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)]

7 Comentarios

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]]

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

No es correcta.

Responder

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]]

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

-- λ> maximoIntercambio 99955421
-- *** Exception: Prelude.head: empty list

-- λ> maximoIntercambio 8522
-- *** Exception: Prelude.head: empty list

-- En lugar de: --

-- λ> maximoIntercambio 99955421
-- 99955412

-- λ> maximoIntercambio 8522
-- 8522

-- λ> maximoIntercambio 99955421

-- *** Exception: Prelude.head: empty list

-- λ> maximoIntercambio 8522

-- *** Exception: Prelude.head: empty list

-- En lugar de: --

-- λ> maximoIntercambio 99955421

-- 99955412

-- λ> maximoIntercambio 8522

-- 8522

Responder

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 _ = []

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 _ = []

Responder

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

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

Responder

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)

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)

Responder

Mayor número obtenido intercambiando dos dígitos

Soluciones

7 Comentarios

Leave a Reply to jaibengueCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

7 Comentarios

Leave a Reply to jaibengueCancel reply

Entradas recientes

Buscar

Correo electrónico