Menu Close

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,

   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.”

George Pólya.

Una solución de “Subconjuntos de orden k

  1. anthormol
    import Data.List
     
    kSubconjuntos :: [a] -> Int -> [[a]]
    kSubconjuntos xs k = [ys | ys <- subsequences xs, length ys == k]

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.