Menu Close

Particiones en listas de segmentos

José A. Alonso,

Exercitium

Definir la función

   particiones :: Int -> [a] -> [[[a]]]

tal que (particiones n xs) es la lista de listas de n elementos cuya concatenación es xs. Por ejemplo,

   ghci> particiones 2 "abc"
   [["","abc"],["a","bc"],["ab","c"],["abc",""]]
   ghci> particiones 3 "abc"
   [["","","abc"],["","a","bc"],["","ab","c"],["","abc",""],
    ["a","","bc"],["a","b","c"],["a","bc",""],["ab","","c"],
    ["ab","c",""],["abc","",""]]
   ghci> length (particiones 4 "abc")
   20

Soluciones

particiones :: Int -> [a] -> [[[a]]]
particiones 0 [] = [[]]
particiones 0 xs = []
particiones n xs = [ys:yss | (ys,zs) <- biparticiones xs,
                             yss <- particiones (n-1) zs]
 
-- (biparticiones xs) es la lista de los pares (xs1,xs2) tales que su
-- concatenación es xs. Por ejemplo, 
--    ghci> biparticiones "abc"
--    [("","abc"),("a","bc"),("ab","c"),("abc","")]
biparticiones :: [a] -> [([a],[a])]
biparticiones []     = [([],[])]
biparticiones (x:xs) = ([],x:xs) :  
                       [(x:xs1,xs2) | (xs1,xs2) <- biparticiones xs]
Medio
,

Una solución de “Particiones en listas de segmentos”

  1. Responder
    Diego 
    import Data.List (inits, tails)
 
particiones :: Int -> [a] -> [[[a]]]
particiones 1 xs = [[xs]]
particiones n xs = concat $ zipWith (x y -> map (x:) (particiones (n-1) y))
                                    (inits xs) (tails xs)

Escribe tu solución

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