Listas con los ceros emparejados

Sea S un conjunto de números. Las listas de ceros emparejados de S son las listas formadas con los elementos de S y en las cuales los ceros aparecen en sublistas de longitud par. Por ejemplo, si S = {0,1,2} entonces [1], [2], [2,1], [2,0,0,2,0,0,1] y [0,0,0,0,1,2] son listas de ceros emparejados de S; pero [0,0,0,2,1,0,0] y [0,0,1,0,1] no lo son.

Definir las funciones

   cerosEmparejados  :: Integer -> Integer -> [[Integer]]
   nCerosEmparejados :: Integer -> Integer -> Integer

1 2	cerosEmparejados :: Integer -> Integer -> [[Integer]] nCerosEmparejados :: Integer -> Integer -> Integer

tales que
+ (cerosEmparejados m n) es la lista de las listas de longitud n de ceros emparejados con los números 0, 1, 2,…, m. Por ejemplo,

     ghci> cerosEmparejados 2 0
     [[]]
     ghci> cerosEmparejados 2 1
     [[1],[2]]
     ghci> cerosEmparejados 3 1
     [[1],[2],[3]]
     ghci> cerosEmparejados 2 2
     [[1,1],[1,2],[2,1],[2,2],[0,0]]
     ghci> cerosEmparejados 2 3
     [[1,1,1],[1,1,2],[1,2,1],[1,2,2],[1,0,0],[2,1,1],[2,1,2],
      [2,2,1],[2,2,2],[2,0,0],[0,0,1],[0,0,2]]
     ghci> cerosEmparejados 2 4
     [[1,1,1,1],[1,1,1,2],[1,1,2,1],[1,1,2,2],[1,1,0,0],[1,2,1,1],
      [1,2,1,2],[1,2,2,1],[1,2,2,2],[1,2,0,0],[1,0,0,1],[1,0,0,2],
      [2,1,1,1],[2,1,1,2],[2,1,2,1],[2,1,2,2],[2,1,0,0],[2,2,1,1],
      [2,2,1,2],[2,2,2,1],[2,2,2,2],[2,2,0,0],[2,0,0,1],[2,0,0,2],
      [0,0,1,1],[0,0,1,2],[0,0,2,1],[0,0,2,2],[0,0,0,0]]

ghci> cerosEmparejados 2 0

[[]]

ghci> cerosEmparejados 2 1

[[1],[2]]

ghci> cerosEmparejados 3 1

[[1],[2],[3]]

ghci> cerosEmparejados 2 2

[[1,1],[1,2],[2,1],[2,2],[0,0]]

ghci> cerosEmparejados 2 3

[[1,1,1],[1,1,2],[1,2,1],[1,2,2],[1,0,0],[2,1,1],[2,1,2],

[2,2,1],[2,2,2],[2,0,0],[0,0,1],[0,0,2]]

ghci> cerosEmparejados 2 4

[[1,1,1,1],[1,1,1,2],[1,1,2,1],[1,1,2,2],[1,1,0,0],[1,2,1,1],

[1,2,1,2],[1,2,2,1],[1,2,2,2],[1,2,0,0],[1,0,0,1],[1,0,0,2],

[2,1,1,1],[2,1,1,2],[2,1,2,1],[2,1,2,2],[2,1,0,0],[2,2,1,1],

[2,2,1,2],[2,2,2,1],[2,2,2,2],[2,2,0,0],[2,0,0,1],[2,0,0,2],

[0,0,1,1],[0,0,1,2],[0,0,2,1],[0,0,2,2],[0,0,0,0]]

(nCerosEmparejados m n) es el número de listas de longitud n de ceros emparejados con los números 0, 1, 2,…, m. Por ejemplo,

     nCerosEmparejados 2 2   ==  5
     nCerosEmparejados 2 3   ==  12
     nCerosEmparejados 2 4   ==  29
     nCerosEmparejados 9 27  ==  79707842493701635611689499

nCerosEmparejados 2 2 == 5

nCerosEmparejados 2 3 == 12

nCerosEmparejados 2 4 == 29

nCerosEmparejados 9 27 == 79707842493701635611689499

Soluciones

import Data.List (genericIndex)
import Data.List (genericLength) 

cerosEmparejados :: Integer -> Integer -> [[Integer]]
cerosEmparejados m 0 = [[]]
cerosEmparejados m 1 = [[k] | k <- [1..m]]
cerosEmparejados m n = 
    [x:ys | x <- [1..m], ys <- cerosEmparejados m (n-1)] ++
    [0:0:ys | ys <- cerosEmparejados m (n-2)]

-- 1ª definición de nCerosEmparejados: 
nCerosEmparejados1 :: Integer -> Integer -> Integer
nCerosEmparejados1 m n = fromIntegral (length (cerosEmparejados m n))

-- 2ª definición de nCerosEmparejados: 
nCerosEmparejados2 :: Integer -> Integer -> Integer
nCerosEmparejados2 _ 0 = 1
nCerosEmparejados2 m 1 = m
nCerosEmparejados2 m n = 
    m * nCerosEmparejados2 m (n-1) + nCerosEmparejados2 m (n-2)

-- 3ª definición de nCerosEmparejados: 
nCerosEmparejados3 :: Integer -> Integer -> Integer
nCerosEmparejados3 m n = aux `genericIndex` n
    where aux = 1 : m : zipWith (\x y -> x+m*y) aux (tail aux)

-- Comparación de eficiencia
--    ghci> nCerosEmparejados1 9 7
--    5144589
--    (22.30 secs, 6556279384 bytes)
--    ghci> nCerosEmparejados2 9 7
--    5144589
--    (0.01 secs, 515464 bytes)
--    ghci> nCerosEmparejados3 9 7
--    5144589
--    (0.01 secs, 518104 bytes)
--
--    ghci> nCerosEmparejados2 9 33
--    45556060883025783396845717812863
--    (21.59 secs, 2676070480 bytes)
--    ghci> nCerosEmparejados3 9 33
--    45556060883025783396845717812863
--    (0.00 secs, 1017240 bytes)

import Data.List (genericIndex)

import Data.List (genericLength)

cerosEmparejados :: Integer -> Integer -> [[Integer]]

cerosEmparejados m 0 = [[]]

cerosEmparejados m 1 = [[k] | k <- [1..m]]

cerosEmparejados m n =

[x:ys | x <- [1..m], ys <- cerosEmparejados m (n-1)] ++

[0:0:ys | ys <- cerosEmparejados m (n-2)]

-- 1ª definición de nCerosEmparejados:

nCerosEmparejados1 :: Integer -> Integer -> Integer

nCerosEmparejados1 m n = fromIntegral (length (cerosEmparejados m n))

-- 2ª definición de nCerosEmparejados:

nCerosEmparejados2 :: Integer -> Integer -> Integer

nCerosEmparejados2 _ 0 = 1

nCerosEmparejados2 m 1 = m

nCerosEmparejados2 m n =

m * nCerosEmparejados2 m (n-1) + nCerosEmparejados2 m (n-2)

-- 3ª definición de nCerosEmparejados:

nCerosEmparejados3 :: Integer -> Integer -> Integer

nCerosEmparejados3 m n = aux `genericIndex` n

where aux = 1 : m : zipWith (\x y -> x+m*y) aux (tail aux)

-- Comparación de eficiencia

-- ghci> nCerosEmparejados1 9 7

-- 5144589

-- (22.30 secs, 6556279384 bytes)

-- ghci> nCerosEmparejados2 9 7

-- 5144589

-- (0.01 secs, 515464 bytes)

-- ghci> nCerosEmparejados3 9 7

-- 5144589

-- (0.01 secs, 518104 bytes)

-- ghci> nCerosEmparejados2 9 33

-- 45556060883025783396845717812863

-- (21.59 secs, 2676070480 bytes)

-- ghci> nCerosEmparejados3 9 33

-- 45556060883025783396845717812863

-- (0.00 secs, 1017240 bytes)

4 Comentarios

Como siempre, hay que intentarlo. Es tremendamente ineficiente pero creo que correcta.

cerosEmparejados :: Integer -> Integer -> [[Integer]]
cerosEmparejados m n = 
    filter (\xs-> and [even $ length xs' | xs' <- group xs,
                                           sum xs' == 0]) 
           $ variacionesR n [0..m]

variacionesR :: Integer -> [a] -> [[a]]
variacionesR _ [] = []
variacionesR 0 _  = [[]]
variacionesR k xs = [y:ys | y <- xs, ys <- variacionesR (k-1) xs]

filter (\xs-> and [even $ length xs' | xs' <- group xs,

sum xs' == 0])

$ variacionesR n [0..m]

variacionesR :: Integer -> [a] -> [[a]]

variacionesR _ [] = []

variacionesR 0 _ = [[]]

variacionesR k xs = [y:ys | y <- xs, ys <- variacionesR (k-1) xs]

Responder

Es algo más rápido que el de Jesús Navas, pero no puede hacer (nCerosEmparejados 9 27). Usar Int en lugar de Integer mejora un poco la rapidez.

import Data.List (genericLength)

cerosEmparejados  :: Integer -> Integer -> [[Integer]]
cerosEmparejados _ 0 = [[]]
cerosEmparejados m n = 
    concatMap (\x -> map (x:) (cerosEmparejados m (n-1))) [1..m]
    ++ if (n > 1) then map ([0,0]++) (cerosEmparejados m (n-2)) else []

nCerosEmparejados :: Integer -> Integer -> Integer
nCerosEmparejados m n = genericLength (cerosEmparejados m n)

-- > nCerosEmparejados 9 7
-- 5144589
-- (12.69 secs, 9761967104 bytes)
-- > nCerosEmparejados 9 8
-- *** Exception: stack overflow

cerosEmparejados _ 0 = [[]]

concatMap (\x -> map (x:) (cerosEmparejados m (n-1))) [1..m]

++ if (n > 1) then map ([0,0]++) (cerosEmparejados m (n-2)) else []

nCerosEmparejados :: Integer -> Integer -> Integer

nCerosEmparejados m n = genericLength (cerosEmparejados m n)

-- > nCerosEmparejados 9 7

-- (12.69 secs, 9761967104 bytes)

-- > nCerosEmparejados 9 8

-- *** Exception: stack overflow

Bueno, ahora que lo pienso, parece que para nCerosEmparejados tenemos que usar fórmula en lugar de length.

nCerosEmparejados :: Integer -> Integer -> Integer
nCerosEmparejados _ 0 = 1
nCerosEmparejados m 1 = m
nCerosEmparejados m n = m * nCerosEmparejados m (n-1) + nCerosEmparejados m (n-2)

nCerosEmparejados _ 0 = 1

nCerosEmparejados m 1 = m

nCerosEmparejados m n = m * nCerosEmparejados m (n-1) + nCerosEmparejados m (n-2)

Un poco más rápida, usando evaluación perezosa

import Data.List (genericIndex)

nCerosEmparejados :: Integer -> Integer -> Integer
nCerosEmparejados m n = suc `genericIndex` n
    where suc = 1 : m : zipWith (\x y -> x+m*y) suc (tail suc)

-- nCerosEmparejados 9 27
-- 79707842493701635611689499
-- (0.01 secs, 2058048 bytes)
-- nCerosEmparejados 12 50
-- 1274522152909116817654271353335641020297962554907616465
-- (0.00 secs, 1065888 bytes)

nCerosEmparejados m n = suc `genericIndex` n

where suc = 1 : m : zipWith (\x y -> x+m*y) suc (tail suc)

-- nCerosEmparejados 9 27

-- 79707842493701635611689499

-- (0.01 secs, 2058048 bytes)

-- nCerosEmparejados 12 50

-- 1274522152909116817654271353335641020297962554907616465

-- (0.00 secs, 1065888 bytes)

Listas con los ceros emparejados

Soluciones

4 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

4 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico