Subconjuntos acotados
Definir la función
|
1 |
subconjuntosAcotados :: [a] -> Int -> [[a]] |
tal que (subconjuntosAcotados xs k) es la lista de los subconjuntos de xs con k elementos como máximo. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 |
λ> subconjuntosAcotados "abcd" 1 ["a","b","c","d",""] λ> subconjuntosAcotados "abcd" 2 ["ab","ac","ad","a","bc","bd","b","cd","c","d",""] λ> subconjuntosAcotados "abcd" 3 ["abc","abd","ab","acd","ac","ad","a", "bcd","bc","bd","b","cd","c","d",""] λ> length (subconjuntosAcotados [1..1000] 2) 500501 λ> length (subconjuntosAcotados2 [1..2000] 2) 2001001 |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
import Data.List (subsequences) -- 1ª definición subconjuntosAcotados1 :: [a] -> Int -> [[a]] subconjuntosAcotados1 xs k = [ys | ys <- subsequences xs , length ys <= k] -- 2ª definición subconjuntosAcotados2 :: [a] -> Int -> [[a]] subconjuntosAcotados2 _ 0 = [[]] subconjuntosAcotados2 [] _ = [[]] subconjuntosAcotados2 (x:xs) k = [x:ys | ys <- subconjuntosAcotados2 xs (k-1)] ++ subconjuntosAcotados2 xs k -- Comparación de eficiencia -- λ> length (subconjuntosAcotados1 [1..25] 2) -- 326 -- (10.48 secs, 6,968,637,480 bytes) -- λ> length (subconjuntosAcotados2 [1..25] 2) -- 326 -- (0.00 secs, 0 bytes) |