Números construidos con los dígitos de un conjunto dado
Definir las siguientes funciones
numerosCon :: [Integer] -> [Integer] numeroDeDigitos :: [Integer] -> Int -> 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)