Menu Close

Reparto de escaños por la ley d’Hont

El sistema D’Hondt es una fórmula creada por Victor d’Hondt, que permite obtener el número de cargos electos asignados a las candidaturas, en proporción a los votos conseguidos.

Tras el recuento de los votos, se calcula una serie de divisores para cada partido. La fórmula de los divisores es V/N, donde V representa el número total de votos recibidos por el partido, y N representa cada uno de los números enteros desde 1 hasta el número de cargos electos de la circunscripción objeto de escrutinio. Una vez realizadas las divisiones de los votos de cada partido por cada uno de los divisores desde 1 hasta N, la asignación de cargos electos se hace ordenando los cocientes de las divisiones de mayor a menor y asignando a cada uno un escaño hasta que éstos se agoten

Definir la función

   reparto :: Int -> [Int] -> [(Int,Int)]

tal que (reparto n vs) es la lista de los pares formados por los números de los partidos y el número de escaño que les corresponden al repartir n escaños en función de la lista de sus votos. Por ejemplo,

   ghci> reparto 7 [340000,280000,160000,60000,15000]
   [(1,3),(2,3),(3,1)]
   ghci> reparto 21 [391000,311000,184000,73000,27000,12000,2000]
   [(1,9),(2,7),(3,4),(4,1)]

es decir, en el primer ejemplo,

  • al 1º partido (que obtuvo 340000 votos) le corresponden 3 escaños,
  • al 2º partido (que obtuvo 280000 votos) le corresponden 3 escaños,
  • al 3º partido (que obtuvo 160000 votos) le corresponden 1 escaño.

Soluciones

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

Pensamiento

Sus cantares llevan
agua de remanso,
que parece quieta.
Y que no lo está;
mas no tiene prisa
por ir a la mar.

Antonio Machado

9 soluciones de “Reparto de escaños por la ley d’Hont

  1. frahidzam
    reparto :: Int -> [Int] -> [(Int,Int)]
    reparto n xs = auxReparto n xs [] xs
     
    auxReparto :: Int -> [Int] -> [(Int,Int)] -> [Int] -> [(Int,Int)]
    auxReparto 0 _ _ _ = []
    auxReparto n xs as ys =  combina [(a,1) | (a,b) <- zip [1..] xs, b == maximum xs] (auxReparto (n-1) ([round (fromIntegral a/fromIntegral (d+1)) | (a,(b,d)) <- zip ys (combina (combina as  [(a,1) | (a,b) <- zip [1..n] xs, b == maximum xs]) (zip [1..length xs] (cycle [0])))]) (combina as  [(a,1) | (a,b) <- zip [1..n] xs, b == maximum xs]) ys) 
     
    combina :: [(Int,Int)] -> [(Int,Int)] -> [(Int,Int)]
    combina [] xs = xs
    combina xs [] = xs
    combina ((a,b):xs) ((c,d):ys) | a == c = [(a, b+d)] ++ combina xs ys
                                  | a < c = [(a,b)] ++ combina xs ((c,d):ys)
                                  | otherwise = [(c,d)] ++ combina ((a,b):xs) ys
    • guicabgod

      En el siguiente ejemplo falla

      λ> reparto 100 [100,200..1000]
      [(1,4),(2,9),(3,14),(4,19),(5,24),(6,29),(7,34),(8,39),(9,50),(10,55)]
      λ> sum (map snd it)
      277

      ya que asigna 277 escaños en lugar de 100.

      • frahidzam

        Ya ha sido solucionado. Ahora si reparte el número de escaños correcto

        reparto :: Int -> [Int] -> [(Int,Int)]
        reparto n xs = auxReparto n xs [] xs
         
        auxReparto :: Int -> [Int] -> [(Int,Int)] -> [Int] -> [(Int,Int)]
        auxReparto 0 _ _ _ = []
        auxReparto n xs as ys =  combina (corrige [(a,1) | (a,b) <- zip [1..] xs, b == maximum xs]) (auxReparto (n-1) ([round (fromIntegral a/fromIntegral (d+1)) | (a,(b,d)) <- zip ys (combina (combina as  (corrige [(a,1) | (a,b) <- zip [1..n] xs, b == maximum xs])) (zip [1..length xs] (cycle [0])))]) (combina as  (corrige [(a,1) | (a,b) <- zip [1..n] xs, b == maximum xs])) ys) 
         
         
        combina :: [(Int,Int)] -> [(Int,Int)] -> [(Int,Int)]
        combina [] xs = xs
        combina xs [] = xs
        combina ((a,b):xs) ((c,d):ys) | a == c = [(a, b+d)] ++ combina xs ys
                                      | a < c = [(a,b)] ++ combina xs ((c,d):ys)
                                      | otherwise = [(c,d)] ++ combina ((a,b):xs) ys
         
         
        corrige xs | xs == [] = [(0,0)]
                   | otherwise = [head xs]
  2. luipromor
     
    reparto :: Int -> [Int] -> [(Int,Int)]
    reparto n vs  = zip [1..] $ g $ aux n [ (1,x,0,x) | x <- vs] 
      where g [] = []
            g ((_,_,c,_):xs) | c /=0 = c : g xs
                             | otherwise = g xs
            aux 0 xs = xs
            aux n xs  = aux (n-1) $ f (encuentraMayor xs (-1)) xs
              where encuentraMayor [] b = b
                    encuentraMayor ((_,_,_,x):xs) y | x >y = encuentraMayor xs x
                                                    | otherwise = encuentraMayor xs y
                    f _ [] = []
                    f a  ((n,x,b,y):xs) | a == y = (n+1,x,b+1,div x (n+1)): f a xs
                                        | otherwise = (n,x,b,y): f a xs
  3. guicabgod

    Como la primera respuesta falla. Por ejemplo,

    λ> reparto 100 [100,200..1000]
    [(1,5),(2,11),(3,16),(4,22),(5,27),(6,33),(7,38),(8,44),(9,50),(10,55)]
    λ> sum (map snd it)
    301

    ya que asigna 301 escaños en lugar de 100.

    • luipromor

      La prueba de la eficacia se deja como prueba al lector

      reparto :: Int -> [Int] -> [(Int,Int)]
      reparto n vs  = zip [1..] $ g $ aux n [ (1,x,0,x) | x <- vs] 
        where g [] = []
              g ((_,_,c,_):xs) | c /=0 = c : g xs
                               | otherwise = g xs
              aux 0 xs = xs
              aux n xs  = aux (n-1) $ f (encuentraMayor xs (-1)) xs
                where encuentraMayor [] b = b
                      encuentraMayor ((_,_,_,x):xs) y | x >y = encuentraMayor xs x
                                                      | otherwise = encuentraMayor xs y
                      f _ [] = []
                      f a  ((n,x,b,y):xs) | a == y = (n+1,x,b+1,div x (n+1)):  xs
                                          | otherwise = (n,x,b,y): f a xs
  4. danmorper2
     
    import Data.Array
    import Data.List
     
    divisiones n xs= [dividir n x |x<-xs]
     
    dividir n x=[(div x i) | i<-[1..n]]
     
    orden n xs = (nub (take n (reverse (sort (concat xs)))))
     
    reparto n xs= takeWhile ((a,b)-> b/=0) [(r,(escaño n r (divisiones n xs))) | r<-[1..(length xs)]]
     
    escaño n r xs =length (intersect (xs!!(r-1)) (orden n xs))
  5. ireprirod
    import Data.List 
     
    reparto :: Int -> [Int] -> [(Int,Int)]
    reparto n ms  = g ((group.sort) (encuentraMax as as (0,0) [] n))
         where as = listaPartidos n ms
               g xss = [(head xs,length xs) | xs<-xss]
     
    listas :: Int -> [Int] -> [[Int]]
    listas _ []     = []
    listas n (x:xs) = [ div x d | d<-[1..n]] : listas n xs
     
    listaPartidos :: Int -> [Int] -> [(Int,Int)]
    listaPartidos n xs = concat (zipWith f (listas n xs) [1..n])
      where f xs n = [(n,x) | x<-xs]
     
    encuentraMax ::
      [(Int,Int)] -> [(Int,Int)] -> (Int,Int) -> [Int] -> Int ->  [Int]
    encuentraMax _ _ _ vs n | length vs == n = vs
    encuentraMax [] [] (a,b) vs n = vs
    encuentraMax [] xs (a,b) vs n = encuentraMax ds ds (0,0) (a:vs) n
      where ds = delete (a,b) xs
    encuentraMax  ((x,y):xs) cs (a,b) vs n
      | y > b      = encuentraMax xs cs (x,y) vs n
      | otherwise  = encuentraMax xs cs (a,b) vs n
  6. javmarcha1
    import Data.List
     
    reparto :: Int -> [Int] -> [(Int,Int)]
    reparto n vs = [(a,aparece a (escaños n vs)) | a <- [1..n],
                    (aparece a (escaños n vs)) /= 0 ]
      where aparece y [] = 0
            aparece y (x:xs) | y == x = 1+ aparece y xs
                             | otherwise = aparece y xs
    escaños :: Int -> [Int] -> [Int]
    escaños n vs = take n (map snd (reverse(sort
                 [(f y/f z,x) | (x,y) <- zip [1..n] vs, z <- [1..n]])))
      where f a = fromIntegral a

Escribe tu solución

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