Particiones en sumas de cuadrados

Definir las funciones

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

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

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

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

1	[nParticionesCuadradas k \| k <- [0..n]]

Por ejemplo, con (graficaParticionesCuadradas 100) se obtiene

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

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

Referencias

Sucesión A001156 de OEIS.

3 Comentarios

Primer intento:

cuadrado n = elem n [x^2|x<-[1..div n 2]]
cuadrados n = [x^2|x<-[1..div n 2],x^2<n]
sublistas :: [a] -> [[a]]
sublistas [] = [[]]
sublistas (x:xs) = (map (x:) (sublistas xs))++(sublistas xs)
aux n [] = []
aux n (x:xs) = (replicate n x)++aux n xs
particionesCuadradas n |cuadrado n = [[n]]++nub [xs|xs<-sublistas(aux n (cuadrados n)),sum xs==n]
                       | otherwise = nub [xs|xs<-sublistas(aux n (cuadrados n)),sum xs==n]

cuadrado n = elem n [x^2|x<-[1..div n 2]]

cuadrados n = [x^2|x<-[1..div n 2],x^2<n]

sublistas :: [a] -> [[a]]

sublistas [] = [[]]

sublistas (x:xs) = (map (x:) (sublistas xs))++(sublistas xs)

aux n [] = []

aux n (x:xs) = (replicate n x)++aux n xs

particionesCuadradas n |cuadrado n = [[n]]++nub [xs|xs<-sublistas(aux n (cuadrados n)),sum xs==n]

| otherwise = nub [xs|xs<-sublistas(aux n (cuadrados n)),sum xs==n]

Responder

import Data.List (tails, genericLength)
import Data.List.Utils (merge)
import Data.Numbers.Primes
import Graphics.EasyPlot
import Math.NumberTheory.Powers.Squares (integerSquareRoot)

-- usando ciertos sumandos `ks` (ord desc), obtiene todas las formas (combinaciones) de sumar `n`
sumaHastaCon :: ℤ → [ℤ] → [[ℤ]]
sumaHastaCon 0 _  = [[]]
sumaHastaCon n ks = concat [(i:) ↥ sumaHastaCon (n-i) fs | fs@(i:_) ← init $ tails ks, n ≥ i]

-- las tres funciones solicitadas
particionesCuadradas :: ℤ → [[ℤ]]
particionesCuadradas n = sumaHastaCon n [i² | i ← [r, r-1…1]] where r = integerSquareRoot n

nParticionesCuadradas :: ℤ → ℤ
nParticionesCuadradas = genericLength ∘ particionesCuadradas

graficaParticionesCuadradas :: ℤ → IO ()
graficaParticionesCuadradas n = plot X11 gfx ↪ η ∘ const ()
             where gfx = Function2D [] [Range 1 $ fromIntegral n, Step 1] (fromIntegral ∘ nParticionesCuadradas ∘ round)

import Data.List (tails, genericLength)

import Data.List.Utils (merge)

import Data.Numbers.Primes

import Graphics.EasyPlot

import Math.NumberTheory.Powers.Squares (integerSquareRoot)

-- usando ciertos sumandos `ks` (ord desc), obtiene todas las formas (combinaciones) de sumar `n`

sumaHastaCon :: ℤ → [ℤ] → [[ℤ]]

sumaHastaCon 0 _ = [[]]

sumaHastaCon n ks = concat [(i:) ↥ sumaHastaCon (n-i) fs | fs@(i:_) ← init $ tails ks, n ≥ i]

-- las tres funciones solicitadas

particionesCuadradas :: ℤ → [[ℤ]]

particionesCuadradas n = sumaHastaCon n [i² | i ← [r, r-1…1]] where r = integerSquareRoot n

nParticionesCuadradas :: ℤ → ℤ

nParticionesCuadradas = genericLength ∘ particionesCuadradas

graficaParticionesCuadradas :: ℤ → IO ()

graficaParticionesCuadradas n = plot X11 gfx ↪ η ∘ const ()

where gfx = Function2D [] [Range 1 $ fromIntegral n, Step 1] (fromIntegral ∘ nParticionesCuadradas ∘ round)

Responder

import Data.List

particionesCuadradas :: Integer -> [[Integer]]
particionesCuadradas 1 = [[1]]
particionesCuadradas n = (nub.map sort) (xss ++ map f xss)
     where cuadrados = map (^2) [1..]
           xss = map (1:) (particionesCuadradas (n-1))
           f ys | take m ys /= replicate m 1 = ys
                | otherwise = sum (take m ys) : drop m ys
                 where m   = (last.takeWhile (<= (length.head.group) ys)) cuadrados

nParticionesCuadradas :: Integer -> Integer
nParticionesCuadradas = genericLength.particionesCuadradas

import Data.List

particionesCuadradas :: Integer -> [[Integer]]

particionesCuadradas 1 = [[1]]

particionesCuadradas n = (nub.map sort) (xss ++ map f xss)

where cuadrados = map (^2) [1..]

xss = map (1:) (particionesCuadradas (n-1))

f ys | take m ys /= replicate m 1 = ys

| otherwise = sum (take m ys) : drop m ys

where m = (last.takeWhile (<= (length.head.group) ys)) cuadrados

nParticionesCuadradas :: Integer -> Integer

nParticionesCuadradas = genericLength.particionesCuadradas

Responder

Particiones en sumas de cuadrados

Soluciones

Referencias

3 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Referencias

Se puede imprimir o compartir con

3 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico