Particiones de enteros positivos
Una partición de un entero positivo n es una manera de escribir n como una suma de enteros positivos. Dos sumas que sólo difieren en el orden de sus sumandos se consideran la misma partición. Por ejemplo, 4 tiene cinco particiones: 4, 3+1, 2+2, 2+1+1 y 1+1+1+1.
Definir la función
particiones :: Int -> [[Int]]
tal que particiones n es la lista de las particiones del número n. Por ejemplo,
particiones 4 == [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]] particiones 5 == [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]] length (particiones 50) == 204226
1. Soluciones en Haskell
import Test.Hspec (Spec, describe, hspec, it, shouldBe) import Test.QuickCheck -- 1ª solución -- =========== particiones1 :: Int -> [[Int]] particiones1 0 = [[]] particiones1 n = [x:y | x <- [n,n-1..1], y <- particiones1 (n-x), [x] >= take 1 y] -- 2ª solución -- =========== particiones2 :: Int -> [[Int]] particiones2 n = aux !! n where aux = [] : map particiones [1..] particiones m = [m] : [x:p | x <- [m,m-1..1], p <- aux !! (m-x), x >= head p] -- 3ª solución -- =========== particiones3 :: Int -> [[Int]] particiones3 n = aux n n where aux 0 _ = [[]] aux n' m = concat [map (i:) (aux (n'-i) i) | i <- [n',n'-1..1], i <= m] -- 4ª solución -- =========== particiones4 :: Int -> [[Int]] particiones4 n = aux n n where aux 0 _ = [[]] aux n' m = concat [map (i:) (aux (n'-i) i) | i <- [k,k-1..1]] where k = min m n' -- Verificación -- ============ verifica :: IO () verifica = hspec spec specG :: (Int -> [[Int]]) -> Spec specG particiones = do it "e1" $ particiones 4 `shouldBe` [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]] it "e2" $ particiones 5 `shouldBe` [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]] spec :: Spec spec = do describe "def. 1" $ specG particiones1 describe "def. 2" $ specG particiones2 describe "def. 3" $ specG particiones3 describe "def. 4" $ specG particiones4 -- La verificación es -- λ> verifica -- 8 examples, 0 failures -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_particiones :: Positive Int -> Bool prop_particiones (Positive n) = all (== particiones1 n) [ particiones2 n , particiones3 n , particiones4 n ] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=20}) prop_particiones -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- -- ========================= -- La comparación es -- λ> length (particiones1 23) -- 1255 -- (12.50 secs, 6,614,487,992 bytes) -- λ> length (particiones2 23) -- 1255 -- (0.04 secs, 3,071,104 bytes) -- λ> length (particiones3 23) -- 1255 -- (0.02 secs, 9,163,544 bytes) -- λ> length (particiones4 23) -- 1255 -- (0.01 secs, 7,149,512 bytes) -- -- λ> length (particiones2 50) -- 204226 -- (2.50 secs, 758,729,104 bytes) -- λ> length (particiones3 50) -- 204226 -- (4.26 secs, 2,359,121,096 bytes) -- λ> length (particiones4 50) -- 204226 -- (2.67 secs, 1,598,588,040 bytes)
2. Soluciones en Python
from timeit import Timer, default_timer # 1ª solución # =========== def particiones1(n: int) -> list[list[int]]: if n == 0: return [[]] return [[x] + y for x in range(n, 0, -1) for y in particiones1(n - x) if not y or x >= y[0]] # 2ª solución # =========== def particiones2(n: int) -> list[list[int]]: def particiones(m: int, aux: list[list[list[int]]]) -> list[list[int]]: return [[m]] + [ [x] + p for x in range(m, 0, -1) for p in aux[m - x] if p and x >= p[0] ] aux: list[list[list[int]]] = [[]] for i in range(1, n + 1): aux.append(particiones(i, aux)) return aux[n] # Verificación # ============ def test_particiones() -> None: for particiones in [particiones1, particiones2]: assert particiones(4) ==\ [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]] assert particiones(5) ==\ [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]] print("Verificado") # La verificación es # >>> test_particiones() # Verificado # Comprobación de equivalencia # ============================ # La propiedad es def test_particiones_equiv(n: int) -> bool: return [particiones1(k) for k in range(1, n)] ==\ [particiones2(k) for k in range(1, n)] # La comprobación es # >>> test_particiones_equiv(20) # True # Comparación de eficiencia -- # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('particiones1(23)') # 4.00 segundos # >>> tiempo('particiones2(23)') # 0.01 segundos