Menu Close

Números construidos con los dígitos de un conjunto dado

José A. Alonso,

Definir las siguientes funciones

   numerosCon      :: [Integer] -> [Integer]
   numeroDeDigitos :: [Integer] -> Integer -> Int

tales que

  • (numerosCon ds) es la lista de los números que se pueden construir con los dígitos de ds (cuyos elementos son distintos elementos del 1 al 9) . Por ejemplo,
     λ> take 22 (numerosCon [1,4,6,9])
     [1,4,6,9,11,14,16,19,41,44,46,49,61,64,66,69,91,94,96,99,111,114]
     λ> take 15 (numerosCon [4,6,9])
     [4,6,9,44,46,49,64,66,69,94,96,99,444,446,449]
     λ> take 15 (numerosCon [6,9])
     [6,9,66,69,96,99,666,669,696,699,966,969,996,999,6666]
  • (numeroDeDigitos ds k) es el número de dígitos que tiene el k-ésimo elemento (empezando a contar en 0) de la sucesión (numerosCon ds). Por ejemplo, 
     numeroDeDigitos [1,4,6,9]   3  ==  1
     numeroDeDigitos [1,4,6,9]   6  ==  2
     numeroDeDigitos [1,4,6,9]  22  ==  3
     numeroDeDigitos [4,6,9]    15  ==  3
     numeroDeDigitos [6,9]      15  ==  4
     numeroDeDigitos [1,4,6,9] (10^(10^5))  ==  166097
     numeroDeDigitos   [4,6,9] (10^(10^5))  ==  209590
     numeroDeDigitos     [6,9] (10^(10^5))  ==  332192

Soluciones

import Data.List (genericIndex, genericLength)
 
-- Definición de numerosCon
-- ========================
 
numerosCon :: [Integer] -> [Integer]
numerosCon xs = [n | n <- [0..]
                   , n `tieneSusDigitosEn` xs]
 
-- (tieneSusDigitosEn xs n) se verifica si los dígitos de n están contenidos en
-- xs. Por ejemplo,
--    4149 `tieneSusDigitosEn` [1,4,6,9]  ==  True
--    4143 `tieneSusDigitosEn` [1,4,6,9]  ==  False
tieneSusDigitosEn :: Integer -> [Integer] -> Bool
tieneSusDigitosEn n xs =
  digitos n `esSubconjunto` xs
 
-- (digitos n) es la lista de los dígitos de n. Por ejemplo,
--    digitos 325  ==  [3,2,5]
digitos :: Integer -> [Integer]
digitos n = [read [c] | c <- show n]
 
-- (esSubconjunto xs ys) se verifica si xs es subconjunto de ys. Por
-- ejemplo, 
--    esSubconjunto [3,2,5] [4,2,5,7,3]  ==  True
--    esSubconjunto [3,2,5] [4,2,5,7]  ==  False
esSubconjunto :: Eq a => [a] -> [a] -> Bool
esSubconjunto xs ys = all (`elem` ys) xs
 
-- 1ª definición de numeroDeDigitos
-- ================================
 
numeroDeDigitos :: [Integer] -> Integer -> Int
numeroDeDigitos xs n =
  length (show (numerosCon xs `genericIndex` n))
 
-- 2ª definición de numeroDeDigitos
-- ================================
 
-- Observando que si el conjunto de dígitos tiene n elementos, entonces
-- hay n^k números con k dígitos.
 
numeroDeDigitos2 :: [Integer] -> Integer -> Int
numeroDeDigitos2 xs n =
  1 + length (takeWhile (<= n) (sumasDePotencias (genericLength xs)))
 
-- (potencia n) son las potencias de n. Por ejemplo,
--    take 5 (potencias 3)  ==  [3,9,27,81,243]
potencias :: Integer -> [Integer]
potencias k = iterate (*k) k 
 
-- (sumasDePotencias n) es la lista de las sumas acumuladas de las
-- potencias de n. Por ejemplo,
--    take 5 (sumasDePotencias 3)  ==  [3,12,39,120,363]
sumasDePotencias :: Integer -> [Integer]
sumasDePotencias k = scanl1 (+) (potencias k)
 
-- Comparación de eficiencia
-- =========================
 
--    λ> numeroDeDigitos [1,4,6,9] 2000
--    6
--    (3.98 secs, 1,424,390,064 bytes)
--    λ> numeroDeDigitos2 [1,4,6,9] 2000
--    6
--    (0.01 secs, 127,464 bytes)
Inicial
, , , , , , , , , , ,

5 soluciones de “Números construidos con los dígitos de un conjunto dado”

  1. Responder
    carriomon1

    La función numeroDeDigitos no es lo suficientemente eficiente como para poder realizar los tres últimos ejemplos

    import Data.Set  as S
import Data.List as L
 
numerosCon :: [Integer] -> [Integer]
numerosCon ds = [x | x <- [1..]
                   , isSubsetOf (fromList (show x)) (fromList dss)]
  where dss = concatMap show ds 
 
numeroDeDigitos :: [Integer] -> Integer -> Int
numeroDeDigitos ds k =
  length (show (last (genericTake k (numerosCon ds))))
    • Responder
      carriomon1 
      numeroDeDigitos :: [Integer] -> Integer -> Int
numeroDeDigitos xs k = fromIntegral (aux xs k 1)
  where aux xs k n
          | genericLength xs ^ n >= k = n
          | otherwise                 = aux xs k (n+1)

      Esta mejora en eficiencia a la anterior pero sigue sin calcular los ejemplos. Llega al orden de 10^(10^4).

  2. Responder
    alerodrod5

    No llega a calcular los últimos ejemplos de numeroDeDigitos

    import Data.List (genericIndex)
 
numerosCon :: [Integer] -> [Integer]
numerosCon xs =
  [x | x <- [minimum xs..], all (`elem` xs) (digitos x)]
  where digitos x = [read [d] | d <- show x] 
 
numeroDeDigitos :: [Integer] -> Integer -> Int
numeroDeDigitos xs x =
  length (show (numerosCon xs `genericIndex` x))
  3. Responder
    angruicam1 
    import Data.List (genericLength)
 
numerosCon :: [Integer] -> [Integer]
numerosCon ds = map read aux
  where dn  = map show ds
        aux = dn ++ mezclas dn aux
        mezclas []     _  = []
        mezclas (x:xs) zs =
          map show (mezcla (map (read . (x++)) zs)
                    (map read (mezclas xs zs)))
 
-- (mezcla xs ys) es la mezcla, eliminando repetidos, de las lista
-- ordenadas xs e ys. Por ejemplo,
mezcla :: [Integer] -> [Integer] -> [Integer]
mezcla []     ys              = ys
mezcla xs     []              = xs
mezcla us@(x:xs) vs@(y:ys) | x == y     = x : mezcla xs ys
                           | x <  y     = x : mezcla xs vs
                           | otherwise  = y : mezcla us ys
 
numeroDeDigitos :: [Integer] -> Integer -> Int
numeroDeDigitos ds k =
  ((_,_,c) -> c) (until ((<= 0)  . ((_,b,_) -> b))
                   ((b,x,n) -> (b*a,x-b,n+1)) (a,k,0))
  where a = genericLength ds
  4. Responder
    pabhueacu 
     
numerosCon      :: [Integer] -> [Integer]
numerosCon xs = xs ++ numerosCon' (f xs xs) xs
    where numerosCon' ys xs = ys ++ numerosCon' (f ys xs) xs
          f ys xs = [y*10+x | y <- ys, x <- xs]
 
numeroDeDigitos :: [Integer] -> Integer -> Int
numeroDeDigitos xs k = aux (genericLength xs) k
  where aux a k = aux2 a (k*(a-1)+a)
        aux2 a s | s < a = 0 
                 | otherwise = 1 + aux2 a (s `div` a)

Escribe tu solución

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