Subconjuntos de orden k
Definir la función
kSubconjuntos :: [a] -> Int -> [[a]]
tal que (kSubconjuntos xs k) es la lista de los subconjuntos de xs con k elementos. Por ejemplo,
λ> kSubconjuntos "bcde" 2 ["bc","bd","be","cd","ce","de"] λ> kSubconjuntos "bcde" 3 ["bcd","bce","bde","cde"] λ> kSubconjuntos "abcde" 3 ["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]
Soluciones
import Data.List (subsequences) -- 1ª definición kSubconjuntos1 :: [a] -> Int -> [[a]] kSubconjuntos1 xs k = [ys | ys <- subsequences xs , length ys == k] -- 2ª definición kSubconjuntos :: [a] -> Int -> [[a]] kSubconjuntos _ 0 = [[]] kSubconjuntos [] _ = [] kSubconjuntos (x:xs) k = [x:ys | ys <- kSubconjuntos xs (k-1)] ++ kSubconjuntos xs k -- Comparación de eficiencia -- λ> length (kSubconjuntos1 [1..24] 3) -- 2024 -- (4.70 secs, 3,489,911,856 bytes) -- λ> length (kSubconjuntos [1..24] 3) -- 2024 -- (0.03 secs, 2,039,488 bytes)