José A. AlonsoDefinir 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,
ghci> kSubconjuntos "bcde" 2 ["bc","bd","be","cd","ce","de"] ghci> kSubconjuntos "bcde" 3 ["bcd","bce","bde","cde"] ghci> 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) |
Otras soluciones
- Se pueden escribir otras soluciones en los comentarios.
- El código se debe escribir entre una línea con <pre lang=”haskell”> y otra con </pre>
Pensamiento
“La belleza en las matemáticas es ver la verdad sin esfuerzo.”
Una solución de “Subconjuntos de orden k”