Ir al contenido principal

Particiones en sumas de cuadrados

Definir las funciones

particionesCuadradas :: Integer -> [[Integer]]
nParticionesCuadradas :: Integer -> Integer
graficaParticionesCuadradas :: Integer -> IO ()

tales que

  • (particionesCuadradas n) es la listas de conjuntos de cuadrados cuya suma es n. Por ejemplo,
particionesCuadradas 3  ==  [[1,1,1]]
particionesCuadradas 4  ==  [[4],[1,1,1,1]]
particionesCuadradas 9  ==  [[9],[4,4,1],[4,1,1,1,1,1],[1,1,1,1,1,1,1,1,1]]
  • (nParticionesCuadradas n) es el número de conjuntos de cuadrados cuya suma es n. Por ejemplo,
nParticionesCuadradas 3    ==  1
nParticionesCuadradas 4    ==  2
nParticionesCuadradas 9    ==  4
nParticionesCuadradas 50   ==  104
nParticionesCuadradas 100  ==  1116
nParticionesCuadradas 200  ==  27482
  • (graficaParticionesCuadradas n) dibuja la gráfica de la sucesión
[nParticionesCuadradas k | k <- [0..n]]

Por ejemplo, con (graficaParticionesCuadradas 100) se obtiene

Particiones en sumas de cuadrados

Soluciones

import Data.List (genericLength)
import Graphics.Gnuplot.Simple

-- Definición de particiones cuadradas
-- ===================================

particionesCuadradas :: Integer -> [[Integer]]
particionesCuadradas n =
    particiones n (reverse $ takeWhile (<=n) cuadrados)

-- cuadrados es la lista de los cuadrados. Por ejemplo,
--    take 12 cuadrados  ==  [1,4,9,16,25,36,49,64,81,100,121,144]
cuadrados :: [Integer]
cuadrados = map (^2) [1..]

-- (particiones n xs) es la lista de las particiones de n como suma de
-- elementos de xs, donde xs es una lista no creciente. Por ejemplo,
--    particiones 10 [7,4,2]  ==  [[4,4,2],[4,2,2,2],[2,2,2,2,2]]
--    particiones 11 [7,4,2]  ==  [[7,4],[7,2,2]]
--    particiones  5 [7,4,2]  ==  []
particiones:: Integer -> [Integer] -> [[Integer]]
particiones _ [] = []
particiones n (x:xs)
    | x >  n    = particiones n xs
    | x == n    = [n] : particiones n xs
    | otherwise = map (x:) (particiones (n-x) (x:xs)) ++ particiones n xs

-- 1ª definición de nParticionesCuadradas
nParticionesCuadradas1 :: Integer -> Integer
nParticionesCuadradas1 = genericLength . particionesCuadradas

-- 2ª definición nParticionesCuadradas
nParticionesCuadradas2 :: Integer -> Integer
nParticionesCuadradas2 n = aux n (reverse $ takeWhile (<=n) cuadrados) where
    aux _ [] = 0
    aux n ys@(x:xs) | x >  n    = aux n xs
                    | x == n    = 1 + aux n xs
                    | otherwise = aux (n-x) ys + aux n xs

-- Comparación de eficiencia
-- =========================

--    λ> nParticionesCuadradas1 250
--    94987
--    (4.21 secs, 3,256,031,528 bytes)
--    λ> nParticionesCuadradas2 250
--    94987
--    (2.93 secs, 1,714,701,504 bytes)

-- Definición de graficaParticionesCuadradas
-- =========================================

graficaParticionesCuadradas :: Integer  -> IO ()
graficaParticionesCuadradas n =
    plotList [Key Nothing] [nParticionesCuadradas2 k | k <- [0..n]]

Referenciasz/h4>