Mínimo número de cambios para igualar una lista
Definir la función
|
1 |
nMinimoCambios :: Ord a => [a] -> Int |
tal que (nMinimoCambios xs) es el menor número de elementos de xs que hay que cambiar para que todos sean iguales. Por ejemplo,
|
1 2 3 4 |
nMinimoCambios [3,5,3,7,9,6] == 4 nMinimoCambios [3,5,3,7,3,3] == 2 nMinimoCambios "Salamanca" == 5 nMinimoCambios (4 : [1..500000]) == 499999 |
En el primer ejemplo, los elementos que hay que cambiar son 5, 7, 9 y 6.
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
import Data.List (group, nub, sort) -- 1ª definición -- ============= nMinimoCambios1 :: Ord a => [a] -> Int nMinimoCambios1 xs = length xs - fst (last (sort (frecuencias xs))) -- (frecuencias xs) es la lista de los pares de los elementos de xs y el -- número de veces que ocurren en xs. Por ejemplo, -- frecuencias [3,5,3,7,9,6] == [(2,3),(1,5),(1,7),(1,9),(1,6)] -- frecuencias [3,5,3,7,5,5] == [(2,3),(3,5),(1,7)] frecuencias :: Ord a => [a] -> [(Int,a)] frecuencias xs = [(cuenta x xs,x) | x <- nub xs] -- (cuenta x ys) es el número de veces que ocurre x en ys. Por ejemplo, -- cuenta 3 [3,5,3,7,9,6] == 2 cuenta :: Ord a => a -> [a] -> Int cuenta x ys = length [y | y <- ys, y == x] -- 2ª definición -- ============= nMinimoCambios2 :: Ord a => [a] -> Int nMinimoCambios2 xs = length xs - fst (last (sort (frecuencias2 xs))) -- (frecuencias2 xs) es la lista de los pares de los elementos de xs y el -- número de veces que ocurren en xs. Por ejemplo, -- frecuencias2 [3,5,3,7,9,6] == [(2,3),(1,5),(1,7),(1,9),(1,6)] -- frecuencias2 [3,5,3,7,5,5] == [(2,3),(3,5),(1,7)] frecuencias2 :: Ord a => [a] -> [(Int,a)] frecuencias2 xs = [(1 + length ys, y) | (y:ys) <- group (sort xs)] -- 3ª definición -- ============= nMinimoCambios3 :: Ord a => [a] -> Int nMinimoCambios3 xs = sum ys - maximum ys where ys = [length ys | ys <- group (sort xs)] |
2 Comentarios