Particiones en listas de segmentos
Exercitium
Definir la función
|
1 |
particiones :: Int -> [a] -> [[[a]]] |
tal que (particiones n xs) es la lista de listas de n elementos cuya concatenación es xs. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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] |