Menu Close

Triángulo de Pascal binario

Los triángulos binarios de Pascal se formas a partir de una lista de ceros y unos usando las reglas del triángulo de Pascal, donde cada uno de los números es suma módulo dos de los dos situados en diagonal por encima suyo. Por ejemplo, los triángulos binarios de Pascal correspondientes a [1,0,1,1,1] y [1,0,1,1,0] son

   1 0 1 1 1   1 0 1 1 0     
    1 1 0 0     1 1 0 1  
     0 1 0       0 1 1   
      1 1         1 0    
       0           1

Sus finales, desde el extremo inferior al extremos superior derecho, son [0,1,0,0,1] y [1,0,1,1,0], respectivamente.

Una lista es Pascal capicúa si es igual a los finales de su triángulo binario de Pascal. Por ejemplo, [1,0,1,1,0] es Pascal capicúa.

Definir las funciones

   trianguloPascalBinario :: [Int] -> [[Int]]
   pascalCapicuas         :: Int -> [[Int]]
   nPascalCapicuas        :: Int -> Integer

tales que

  • (trianguloPascalBinario xs) es el triágulo binario de Pascal correspondiente a la lista xs. Por ejemplo,
     λ> trianguloPascalBinario [1,0,1,1,1]
     [[1,0,1,1,1],[1,1,0,0],[0,1,0],[1,1],[0]]
     λ> trianguloPascalBinario [1,0,1,1,0]
     [[1,0,1,1,0],[1,1,0,1],[0,1,1],[1,0],[1]]
  • (pascalCapicuas n) es la lista de listas de Pascal capicúas de n elementos. Por ejemplo,
     λ> pascalCapicuas 2
     [[0,0],[1,0]]
     λ> pascalCapicuas 3
     [[0,0,0],[0,1,0],[1,0,0],[1,1,0]]
     λ> pascalCapicuas 4
     [[0,0,0,0],[0,1,1,0],[1,0,0,0],[1,1,1,0]]
  • (nPascalCapicuas n) es el número de listas de Pascal capicúas de n elementos. Por ejemplo,
     λ> nPascalCapicuas 2
     2
     λ> nPascalCapicuas 3
     4
     λ> nPascalCapicuas 4
     4
     λ> nPascalCapicuas 400
     1606938044258990275541962092341162602522202993782792835301376
     λ> length (show (nPascalCapicuas (10^5)))
     15052
     λ> length (show (nPascalCapicuas (10^6)))
     150515
     λ> length (show (nPascalCapicuas (10^7)))
     1505150

Soluciones

import Data.List (genericLength, unfoldr)
 
-- Definición de trianguloPascalBinario
-- ====================================
 
trianguloPascalBinario :: [Int] -> [[Int]]
trianguloPascalBinario xs =
  takeWhile (not . null) (iterate siguiente xs)
 
-- (siguiente xs) es la línea siguiente a la xs en el triángulo binario
-- de Pascal. Por ejemplo,
--    λ> siguiente [1,0,1,1,1]
--    [1,1,0,0]
--    λ> siguiente it
--    [0,1,0]
--    λ> siguiente it
--    [1,1]
--    λ> siguiente it
--    [0]
--    λ> siguiente it
--    []
--    λ> siguiente it
--    []
siguiente :: [Int] -> [Int]
siguiente xs = [(x + y) `mod` 2 | (x,y) <- zip xs (tail xs)]
 
-- 2ª definición de trianguloPascalBinario
-- =======================================
 
trianguloPascalBinario2 :: [Int] -> [[Int]]
trianguloPascalBinario2 = unfoldr f 
  where f [] = Nothing
        f xs = Just (xs, siguiente xs)
 
-- Definición de pascalCapicuas
-- ============================
 
pascalCapicuas :: Int -> [[Int]]
pascalCapicuas n =
  [xs | xs <- inicios n
      , esPascalCapicua xs]
 
-- (inicios n) es la lista de longitud n formadas por ceros y unos. Por
-- ejemplo, 
--    λ> inicios 0
--    [[]]
--    λ> inicios 1
--    [[0],[1]]
--    λ> inicios 2
--    [[0,0],[0,1],[1,0],[1,1]]
--    λ> inicios 3
--    [[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]
inicios :: Int -> [[Int]]
inicios 0 = [[]]
inicios n = map (0:) xss ++ map (1:) xss
  where xss = inicios (n-1)
 
-- Otra forma de definir inicios es
inicios2 :: Int -> [[Int]]
inicios2 n = sucInicios !! n
  where sucInicios    = iterate siguiente [[]]
        siguiente xss = map (0:) xss ++ map (1:) xss
 
-- (esPascalCapicua xs) se verifica si xs es una lista de Pascal
-- capicúa. Por ejemplo, 
--    esPascalCapicua [1,0,1,1,0]  ==  True
--    esPascalCapicua [1,0,1,1,1]  ==  False
esPascalCapicua :: [Int] -> Bool
esPascalCapicua xs =
  xs == finalesTrianguloPascalBinario xs
 
-- (finalesTrianguloPascalBinario xs) es la inversa de la lista de los
-- finales del triángulo binarios de xs. Por ejemplo,
--    λ> finalesTrianguloPascalBinario [1,0,1,1,1]
--    [0,1,0,0,1]
finalesTrianguloPascalBinario :: [Int] -> [Int]
finalesTrianguloPascalBinario =
  reverse . map last . trianguloPascalBinario
 
-- 1ª definición de nPascalCapicuas
-- ================================
 
nPascalCapicuas :: Int -> Integer
nPascalCapicuas =
  genericLength . pascalCapicuas
 
-- 2ª definición de nPascalCapicuas
-- ================================
 
nPascalCapicuas2 :: Int -> Integer
nPascalCapicuas2 n =
  2 ^ ((n + 1) `div` 2)

Pensamiento

La envidia de la virtud
hizo a Caín criminal.
¡Gloria a Caín! Hoy el vicio
es lo que se envidia más.

Antonio Machado

4 soluciones de “Triángulo de Pascal binario

  1. frahidzam
    import Control.Monad (replicateM)
     
    trianguloPascalBinario :: [Int] -> [[Int]]
    trianguloPascalBinario xs =
      takeWhile (not . null) (iterate f xs)
      where f [x]      = []
            f (x:y:xs) = (mod (x+y) 2) : f (y:xs)
     
    pascalCapicuas :: Int -> [[Int]]
    pascalCapicuas n =
      filter capicuaPascal (replicateM n [0,1])
     
    capicuaPascal :: [Int] -> Bool
    capicuaPascal xs =
      xs == reverse (map last (trianguloPascalBinario xs))
     
    nPascalCapicuas :: Int -> Integer
    nPascalCapicuas n =
       2^(div (n+1) 2)
  2. adogargon
    import Data.List
     
    trianguloPascalBinario :: [Int] -> [[Int]]
    trianguloPascalBinario []  = []
    trianguloPascalBinario [x] = [[x]]
    trianguloPascalBinario xs  =
      xs : trianguloPascalBinario (map sumaV (adyacentes xs))
     
    adyacentes :: [Int] -> [(Int,Int)]
    adyacentes xs = zip xs (tail xs)
     
    sumaV :: (Int,Int) -> Int
    sumaV (a,b) = (a + b) `mod` 2
     
    pascalCapicuas :: Int -> [[Int]]
    pascalCapicuas n = filter capicua (generador n)
     
    generador :: Int -> [[Int]]
    generador 0 = []
    generador 1 = [[0],[1]]
    generador n = [0:xs | xs <- generador (n-1)] ++
                  [1:xs | xs <- generador (n-1)]
     
    capicua :: [Int] -> Bool
    capicua xs = xs == finales (trianguloPascalBinario xs)
     
    finales :: [[Int]] -> [Int]
    finales  = reverse . map last
     
    nPascalCapicuas :: Int -> Integer
    nPascalCapicuas n = genericLength (pascalCapicuas n)
  3. luipromor
    import Data.List (nub, permutations)
     
    trianguloPascalBinario :: [Int] -> [[Int]]
    trianguloPascalBinario xs = init (xs: aux xs [])
      where aux [] []       = []
            aux [x] ys      = reverse ys : aux (reverse ys) []
            aux (x:y:xs) ys = aux (y:xs) (mod (x+y) 2 : ys)
     
    pascalCapicuas :: Int -> [[Int]]
    pascalCapicuas x =
      concat [nub  [ys | ys <- permutations xs ,esCapicua ys] | xs <- aux x 0]
      where
        esCapicua xs = map last (reverse (trianguloPascalBinario xs)) == xs
        aux x n | x == n = [replicate n 1]
                | otherwise = (replicate n 1 ++ replicate (x-n) 0) : aux x (n+1)
     
    nPascalCapicuas :: Int -> Integer
    nPascalCapicuas = genericLength . pascalCapicuas
  4. berarcmat
    trianguloPascalBinario :: [Int] -> [[Int]]
    trianguloPascalBinario xs =
      takeWhile (/= []) (iterate adyacentesSumaBinario xs)
     
    adyacentesSumaBinario :: [Int] -> [Int]
    adyacentesSumaBinario xs = [(a + b) `mod` 2 | (a,b) <- zip xs (tail xs)]
     
    pascalCapicuas :: Int -> [[Int]]
    pascalCapicuas n = [xs | xs <- digitos n, esPascalCapicua xs]
     
    digitos :: Int -> [[Int]]
    digitos 0 = [[]]
    digitos n = map (0:) xss ++ map (1:) xss
      where xss = digitos (n-1)
     
    esPascalCapicua :: [Int] -> Bool
    esPascalCapicua xs = xs == reverse (map last ys)
      where ys = trianguloPascalBinario xs
     
    nPascalCapicuas :: Int -> Integer
    nPascalCapicuas = genericLength . pascalCapicuas

Leave a Reply

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