哈斯克尔组合和排列 [英] Haskell combinations and permutation

问题描述

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

例如，对于5个集合，我将拥有

  ** [[aaaaa]，[aaaab]，[aaaac]，[aaabc]，.....] ** etc 3 ^ 5 = 243个组合
  

上面的aaaaaa基本上是a，a，a，a，a。 ...当然，nanothief的答案给出了最短的解决方案，但它自己做起来可能很有教育意义和有趣。

有很多方法可以为笛卡尔积写一个函数。例如。您可以使用列表推导：

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

其中 +）:: [a] - > [a] - > [a] - 请参阅 Data.List 。另一种可能性是使用list的 Applicative 实例：

  import Control 。适用性
 
 prod as bs =（++）< $>作为< *> 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，
  - bacbbabbbbbcbcabcbbcccaacabcaccba
 cbb，cbc，cca，ccb，ccc] 
  

解决方案可能比采用 replicateM 捷径更有价值。也就是说，您可以轻松使用 Hoogle 。

-

有关Functors和Applicative的更多信息，请参阅定义 fmap （< $> ）和 ap （< * GT; ）。 函数，应用程序和图片中的Monad 也可以是一个很好的资源。

I have three word in a list ["a","b","c"]. i want to find all possible combination in set 5,6 etc.

for example for set of 5 i would have

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

aaaaaa above will basically be "a","a","a","a","a" ....

解决方案

Of course, nanothief's answer gives the shortest solution, but it might be instructive and fun to do it yourself.

There are many ways to write a function for the cartesian product. E.g. you can use list comprehensions:

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

Where (++) :: [a] -> [a] -> [a] -- see Data.List. Another possibility is to use the Applicative instance of list:

import Control.Applicative

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

Now you need to apply this operation repeatedly. A fold can do this, e.g.:

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"]

Understanding this solution might be more valuable than taking the replicateM short cut. That said, you could have found the latter easily using Hoogle.

--

For more on Functors and Applicative see definitions fmap (<$>) and ap (<*>). Functors, Applicatives, And Monads In Pictures can also be a good resource.

这篇关于哈斯克尔组合和排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！