Haskell组合和排列

Question

我在列表中有三个单词["a","b","c"].我想在第5,6等集中找到所有可能的组合.

例如,我将拥有5件套

**[ [aaaaa],[aaaab],[aaaac], [aaabc] , ..... ]** etc 3 ^ 5 = 243 combinations

上面的aaaaaa基本上是"a","a","a","a","a"....

Answer 1

replicateM 做你想要的:

> import Control.Monad
> replicateM 5 ["a", "b", "c"]
[["a","a","a","a","a"],["a","a","a","a","b"],["a","a","a","a","c"],["a","a","a","b","a"],["a","a","a","b","b"],["a","a","a","b","c"],["a","a","a","c","a"],["a","a","a","c","b"],["a","a","a","c","c"],["a","a","b","a","a"],["a","a","b","a","b"],["a","a","b","a","c"],["a","a","b","b","a"],["a","a","b","b","b"],["a","a","b","b","c"]...]

Answer 2

当然,nanothief的答案提供了最短的解决方案,但是自己做这件事可能是有益的,也很有趣.

有很多方法可以为笛卡尔积编写函数.例如,您可以使用列表推导:

prod :: [[a]] -> [[a]] -> [[a]]
prod as bs = [a ++ b | a <- as, b <- bs]

Where (++) :: [a] -> [a] -> [a]- 请参阅Data.List.另一种可能是使用Applicativelist 的实例:

import Control.Applicative

prod as bs = (++) <$> as <*> bs

现在您需要重复应用此操作.折叠可以做到这一点,例如:

rep :: Int -> [[a]] -> [[a]]
rep n as = foldr1 prod $ replicate n as

rep 3 ['a','b','c']
--["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"]

理解这个解决方案可能比采取replicateM捷径更有价值.也就是说,您可以轻松地使用Hoogle找到后者.

-

有关Functors和Applicative的更多信息,请参阅定义fmap(<$>)和ap(<*>).Functors,Applicatives和Monads In Pictures也是一个很好的资源.