import Data.List (sort, group)
-- Para los ejemplos que siguen, se usará la siguiente ditribución de
-- votos entre 5 partidos.
ejVotos :: [Int]
ejVotos = [340000,280000,160000,60000,15000]
-- 1ª solución
-- ===========
reparto :: Int -> [Int] -> [(Int,Int)]
reparto n vs =
[(x,1 + length xs) | (x:xs) <- group (sort (repartoAux n vs))]
-- (repartoAux n vs) es el número de los partidos, cuyos votos son vs, que
-- obtienen los n escaños. Por ejemplo,
-- ghci> repartoAux 7 ejVotos
-- [1,2,1,3,2,1,2]
repartoAux :: Int -> [Int] -> [Int]
repartoAux n vs = map snd (repartoAux' n vs)
-- (repartoAux' n vs) es la lista formada por los n restos mayores
-- correspondientes a la lista de votos vs. Por ejemplo,
-- ghci> repartoAux' 7 ejVotos
-- [(340000,1),(280000,2),(170000,1),(160000,3),(140000,2),(113333,1),
-- (93333,2)]
repartoAux' :: Int -> [Int] -> [(Int,Int)]
repartoAux' n vs =
take n (reverse (sort (concatMap (restos n) (votosPartidos vs))))
-- (votosPartidos vs) es la lista con los pares formados por los votos y
-- el número de cada partido. Por ejemplo,
-- ghci> votosPartidos ejVotos
-- [(340000,1),(280000,2),(160000,3),(60000,4),(15000,5)]
votosPartidos :: [Int] -> [(Int,Int)]
votosPartidos vs = zip vs [1..]
-- (restos n (x,i)) es la lista obtenidas dividiendo n entre 1, 2,..., n.
-- Por ejemplo,
-- ghci> restos 5 (340000,1)
-- [(340000,1),(170000,1),(113333,1),(85000,1),(68000,1)]
restos :: Int -> (Int,Int) -> [(Int,Int)]
restos n (x,i) = [(x `div` k,i) | k <- [1..n]]
-- 2ª solución
-- ===========
reparto2 :: Int -> [Int] -> [(Int,Int)]
reparto2 n xs =
( map (\x -> (head x, length x))
. group
. sort
. map snd
. take n
. reverse
. sort
) [(x `div` i, p) | (x,p) <- zip xs [1..], i <- [1..n]] |