Menu Close

Índice del menor elemento a eliminar para que la suma sea divisible por K

Definir la función

   indice :: [Int] -> Int -> Maybe Int

tal que (indice xs k) es el índice del menor elemento a eliminar de la lista de enteros positivos xs para que la suma de los restantes sea divisible por k o Nothing, si no existe dicho elemento. Por ejemplo,

   indice [1,8,4,1] 2         ==  Just 2
   indice [4,6,7,5,7] 11      ==  Just 2
   indice [4,6,7,5,7] 12      ==  Just 3
   indice [4,6,7,5,7] 13      ==  Nothing
   indice [1..10^7] 7         ==  Just 5
   indice [10^7,10^7-1..1] 7  ==  Just 9999994

Soluciones

import Test.QuickCheck
import Data.List (sort)
import Data.Maybe (listToMaybe)
 
-- 1ª solución
-- ===========
 
indice :: [Int] -> Int -> Maybe Int
indice xs k
  | null ys   = Nothing
  | otherwise = Just (head ys)
  where ys = [i | (_,i,zs) <- sort (eliminaciones xs),
                  sum zs `mod` k == 0]
 
-- (eliminaciones xs) es la lista de ternas (x,i,zs) tales que x es un
-- elemento de xs, i es la posición de x en xs y zs es la lista de los
-- restantes elementos de xs. Por ejemplo,
--    λ> eliminaciones [5,7,6,5]
--    [(5,0,[7,6,5]),(7,1,[5,6,5]),(6,2,[5,7,5]),(5,3,[5,7,6])]
eliminaciones :: [a] -> [(a,Int,[a])]
eliminaciones xs = [(z,i,zs) | ((z,zs),i) <- zip (aux xs) [0..]]
  where aux []       = []
        aux [x]      = [(x,[])]
        aux (x:y:zs) = (x,y:zs) : [(v,x:vs) | (v,vs) <- aux (y:zs)]
 
-- 2ª solución
-- ===========
 
indice2 :: [Int] -> Int -> Maybe Int
indice2 xs k
  | null ys   = Nothing
  | otherwise = Just (head ys)
  where d = sum xs `mod` k
        ys = [i | (x,i) <- sort (zip xs [0..]),
                  x `mod` k == d]
 
-- 3ª solución
-- ===========
 
indice3 :: [Int] -> Int -> Maybe Int
indice3 xs k = listToMaybe ys
  where d = sum xs `mod` k
        ys = [i | (x,i) <- sort (zip xs [0..]),
                  x `mod` k == d]
 
-- Comprobación de la equivalencia
-- ===============================
 
-- La propiedad es
prop_equivalencia :: [Int] -> Int -> Bool
prop_equivalencia xs k =
  indice  xs' k' == indice2 xs' k' &&
  indice2 xs' k' == indice3 xs' k'
  where xs' = map ((+1) . abs) xs
        k'  = 1 + abs k
 
-- La comprobación es
--    λ> quickCheck prop_equivalencia
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> indice [1..5000] 7
--    Just 2
--    (2.82 secs, 2,458,555,104 bytes)
--    λ> indice2 [1..5000] 7
--    Just 2
--    (0.01 secs, 1,991,232 bytes)
--    λ> indice3 [1..5000] 7
--    Just 2
--    (0.01 secs, 1,991,072 bytes)

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Medio

5 soluciones de “Índice del menor elemento a eliminar para que la suma sea divisible por K

  1. Rubén Muñoz Mkrtchian
    -- 1ª Definición:
    -- =============
     
    indice1 :: [Int] -> Int -> Maybe Int
    indice1 xs k
      | null listaAuxiliar = Nothing
      | otherwise          = Just (pos (minimum listaAuxiliar) xs)
          where listaAuxiliar = aux1 xs k (sum xs)
     
    -- aux1 es la lista de los elementos x de xs tales que n-x es divisible por
    -- k. Por ejemplo,
    --   λ> aux1 [3,7,5,2] 2 17
    --   [3,7,5]
     
    aux1 :: [Int] -> Int -> Int -> [Int]
    aux1 xs k n = [x | x <- xs, mod (n-x) k == 0]
     
    -- pos y xs es la posición del elemento y en la lista xs. Para la función
    -- indice1 en este caso no es necesario definir el caso base en el que y no
    -- pertenece a xs. Por ejemplo,
    --   λ> pos 4 [1..10]
    --   3
     
    pos :: Int -> [Int] -> Int
    pos y (x:xs)
      | y == x    = 0
      | otherwise = 1 + pos y xs
     
    -- 2ª Definición:
    -- =============
     
    indice2 :: [Int] -> Int -> Maybe Int
    indice2 xs k
      | null listaAuxiliar = Nothing
      | otherwise          = Just (snd (minimum listaAuxiliar))
          where listaAuxiliar = aux2 xs k (sum xs)
     
    -- aux2 xs k n es la lista de pares (x,i) tales que n-x es divisible por k,
    -- siendo i la posición de cada elemento x que satisface dicha condición. Por
    -- ejemplo,
    --   λ> aux2 [3,7,5,2] 2 17
    --   [(3,0),(7,1),(5,2)]
     
    aux2 :: [Int] -> Int -> Int -> [(Int,Int)]
    aux2 xs k n = [(x,i) | (x,i) <- zip xs [0..], mod (n-x) k == 0]
     
    -- Comparación de eficiencia:
    -- =========================
     
    -- Ambas funciones tardan bastante en calcular los dos últimos ejemplos. Se
    -- observa además que la eficiencia de indice1 varía en gran medida en función
    -- de cuál sea la posición buscada, mientras que indice2 parece tener una
    -- eficiencia independiente de dicha posición.
    --   λ> indice1 [1..10^7] 7
    --   Just 5
    --   (10.40 secs, 3,979,876,384 bytes)
    --   λ> indice2 [1..10^7] 7
    --   Just 5
    --   (13.43 secs, 5,637,884,632 bytes)
    --   λ> indice1 [10^7,10^7-1..1] 7
    --   Just 9999994
    --   (17.01 secs, 6,244,765,128 bytes)
    --   λ> indice2 [10^7,10^7-1..1] 7
    --   Just 9999994
    --   (13.69 secs, 5,637,890,520 bytes)
  2. Joaquín Infante Rodríguez
    import Data.Maybe
    import Data.List
     
    indice :: [Int] -> Int -> Maybe Int
    indice xs x | eliminaDivisible xs x == [] = Nothing
                | otherwise                   = Just (minimo (eliminaDivisible xs x))
     
    eliminaDivisible :: [Int] -> Int -> [(Int,Int)]
    eliminaDivisible [] x = []
    eliminaDivisible xs x = [(y,n) | (y,n) <- zip xs [0..], rem (sum (delete y xs)) x == 0]
     
    minimo :: [(Int,Int)] -> Int
    minimo [] = (-1)
    minimo xs = snd (head [(y,n) | (y,n) <- xs , y== minimum (map fst xs)])
  3. Cristina Gómez Cirera
    import Data.List
     
    indiceA4 :: [Int] -> Int -> Maybe Int
    indiceA4 xs k  | null t = Nothing
                   |otherwise = Just (head t)
      where t = indices xs k
     
    -- indices xs k es la lista de los  índices de los elementos de xs tales que al ser
    -- eliminados, la suma de los restantes es múltiplo de k
    --    λ> indices [4,6,7,5,7] 11
    --    [2,4]
    indices xs k =  [i | (x,i) <- ys ,(t-x) `mod`k == 0]
      where t  = sumaConPatron xs
            ys = sort (zip xs [0..])
     
    -- sumaConPatron xs es la suma de la lista xs, calculándola por la fórmula de la
    -- progresión aritmética en caso de que se pueda
    --    λ> sumaConPatron [1..10^7]
    --    50000005000000
    sumaConPatron xs | x:y:ys == [x,y..z] = (x + z)*(length xs) `div` 2
                     | otherwise          = sum xs
      where (x:y:ys) = xs
            z        = last xs
    • José A. Alonso

      La definición es incorrecta. Por ejemplo,

      λ> indice [1] 1
      *** Exception: Irrefutable pattern failed for pattern x : y : ys
  4. Alejandro García Alcaide
    -- La funcion quedaria: 
    indice :: [Int] -> Int -> Maybe Int
    indice xs k | not (algunoDivisible ys k) = Nothing
                | otherwise  =  Just (posicion (maximum (listaDivisibles ys k)) ys)
     where ys = sumaCombinaciones xs
     
     
     
    -- La funcion posicion x xs da el lugar en el que se encuentra el elemento x en
    -- la lista xs. Por ejemplo:
    -- posicion 8 [1..8] == 7
     
    posicion :: Int -> [Int] -> Int
    posicion k (x:xs) | k == x    = 0
                      | otherwise = 1 + posicion k xs
     
     
    -- La funcion algunoDivisible verifica si algun elemento de la lista es
    -- divisible entre y. La funcion listaDivisibles toma ese elemento.
    -- algunoDivisible [1..5] 2 == True
    -- listaDivisibles [1..5] 2 == [2,4]
     
    listaDivisibles :: [Int] -> Int -> [Int]
    listaDivisibles []     _                = []
    listaDivisibles (x:xs) y | mod x y == 0 = x :(listaDivisibles xs y)
                             | otherwise    = listaDivisibles xs y
     
     
    algunoDivisible []     _ = False
    algunoDivisible (x:xs) y | mod x y == 0 = True
                             | otherwise    = algunoDivisible xs y
     
    -- Con sumaCombinaciones, por su parte, obtenemos la suma de los elementos de las distintas
    -- listas formadas con combinaciones. 
    sumaCombinaciones :: [Int] -> [Int]
    sumaCombinaciones xs = map sum (combinaciones xs) 
     
     
    -- Por otro lado, la funcion combinaciones nos da las distintas listas que se pueden forman
    -- quitando un elemento de la lista original xs. Por ejemplo:
    -- combinaciones [1..4] == [[2,3,4],[1,3,4],[1,2,4],[1,2,3]]
    combinaciones :: [a] -> [[a]]
    combinaciones xs = [elimina n xs | n <- [1..p]]
     where p = length xs
     
    -- Por ultimo, la funcion elimina n xs elimina el n-esimo elemento de la lista xs. Por
    -- ejemplo:
    -- elimina 5 [1..7] == [1,2,3,4,6,7]
    -- elimina 3 [4..8] == [4,5,7,8]
    elimina :: (Eq t, Num t) => t -> [a] -> [a]
    elimina _ []     = []
    elimina n (x:xs) | n == 1    = xs
                     | otherwise = x: elimina (n-1) xs

Leave a Reply

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