Permutaciones de una lista - Haskell

Quiero hacer todas las combinaciones posibles de subgrupos con 2 listas. Aquí es una función que hace precisamente esto:Permutaciones de una lista - Haskell

getCombinations :: [a] -> [[a]] 
getCombinations na = do 
    a <- na 
    b <- na 
    [[a,b]]

Si pasa "abc" para esta función, devuelve lo siguiente:

["aa","ab","ac","ba","bb","bc","ca","cb","cc"]

Una simple modificación del mismo método podría volver combinaciones de 3 listas en lugar de dos

getCombinations :: [a] -> [[a]] 
getCombinations na = do 
    a <- na 
    b <- na 
    c <- na 
    [[a,b,c]]

resultado de pasar "abc" como argumento:

["aaa","aab","aac","aba","abb","abc","aca","acb","acc", 
"baa","bab","bac","bba","bbb","bbc","bca","bcb","bcc", 
"caa","cab","cac","cba","cbb","cbc","cca","ccb","ccc"]

¿Cuál es la forma más sencilla de hacerlo escalar a un número arbitrario de las listas? Esto es lo que la declaración de tipo debe ser similar:

getCombinations :: Int -> [a] -> [[a]]

Fuente

2012-01-08 RooSoft

Siempre puedes intentar utilizar hoogle: http://www.haskell.org/hoogle/?hoogle=Int+-%3E+[a]+-%3E+[[a]], da replicateM como tercer resultado. – sdcvvc

Gracias sdcvvc, ¡no sabía que era posible consultar hoogle de esa manera! – RooSoft

Técnicamente, estas son [Permutaciones] (https://en.wikipedia.org/wiki/Permutation) NOT [Combinaciones] (https://en.wikipedia.org/wiki/Combination). Los matemáticos serán pedantes ... –

Lo que queremos es replicateM:

replicateM :: Int -> m a -> m [a]

la definición es tan simple como:

replicateM n = sequence . replicate n

por lo que es sequence en la lista mónada que está haciendo el trabajo real aquí.

Fuente

2012-01-08 17:54:03 ehird

Ese es exactamente el tipo de respuesta que estaba buscando. Muchas gracias ehird! – RooSoft

@RooSoft ¿Por qué esperarías algo menos? Especialmente en SO. Especialmente para la etiqueta [haskell] (la etiqueta más amigable en SO). –

Qué cruel de ti, avergonzarme así. Esto es lo que tuve: '\ i l-> iterate (ap (fmap (:) l)) [[]] !! i' T_T – Rotsor

Para aquellos que vienen aquí para la función combination, un k: combinación de un conjunto S es un subconjunto de k elementos distintos de S , tenga en cuenta que el orden no es importante.

Elija k elementos de n elementos es igual a elegir k - 1 elementos de n - 1 elementos, además de elegir k elementos de n - 1 elementos.

enter image description here

Utilice esta definición recursiva, podemos escribir: pregunta

combinations :: Int -> [a] -> [[a]] 
combinations k xs = combinations' (length xs) k xs 
    where combinations' n k' [email protected](y:ys) 
      | k' == 0 = [[]] 
      | k' >= n = [l] 
      | null l = [] 
      | otherwise = map (y :) (combinations' (n - 1) (k' - 1) ys) ++ combinations' (n - 1) k' ys 


ghci> combinations 5 "abcdef" 
["abcde","abcdf","abcef","abdef","acdef","bcdef"]

del op es un repetidas permutaciones, que alguien ya ha dado una respuesta. Para la permutación no repetida, use permutations de Data.List.

Fuente

2014-03-22 11:44:56

Permutaciones de una lista - Haskell

Respuesta

Cuestiones relacionadas