Exercitium
Definir la función
particiones :: Int -> [a] -> [[[a]]] |
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 |
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] |
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]
Se puede imprimir o compartir con
Una solución de “Particiones en listas de segmentos”