Subconjuntos de orden k
Definir la función
|
1 |
kSubconjuntos :: [a] -> Int -> [[a]] |
tal que (kSubconjuntos xs k) es la lista de los subconjuntos de xs con k elementos. Por ejemplo,
|
1 2 3 4 5 6 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
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.»
Un comentario