列表的排列--Haskell

我想使所有可能的子组与2个列表的组合。这里，不只是这一个功能：列表的排列--Haskell

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

如果传递“ABC”这个功能，它返回：

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

同样的方法的简单修改可以返回的3所列出的组合而不是两个。通过“ABC”作为参数的

getCombinations :: [a] -> [[a]] 
getCombinations na = do 
    a <- na 
    b <- na 
    c <- na 
    [[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"]

什么让它扩展到列表中任意数量的最简单的方法？下面是类型声明应该是什么样子：

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

来源

2012-01-08 RooSoft

您可以随时尝试使用hoogle：http://www.haskell.org/hoogle/?hoogle=Int+-%3E+[a]+-%3E+[[a]]，它会将replicateM作为第三个结果。 – sdcvvc 2012-01-08 18:00:34

谢谢sdcvvc，我不知道有可能像这样查询hoogle！ – RooSoft 2012-01-08 18:16:42

从技术上讲，这些是[置换]（https://en.wikipedia.org/wiki/Permutation）不是[组合]（https://en.wikipedia.org/wiki/Combination）。数学家将是迂腐的... – 2014-01-22 23:48:24

你想要的是replicateM：

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

的定义简单：

replicateM n = sequence . replicate n

所以它sequence名单monad在这里做着真正的工作。

来源

2012-01-08 17:54:03 ehird

这正是我寻找的那种渴望。非常感谢ehird！ – RooSoft 2012-01-08 18:02:00

@RooSoft你为什么期望更少？特别是在SO上。特别是[haskell]标签（SO上最友好的标签）。 – 2012-01-09 05:32:51

你有多残忍，让我感到尴尬。这就是我所拥有的：'\ I l-> iterate（ap（fmap（:) l））[[]] !! i'T_T – Rotsor 2012-01-09 18:14:31

对于那些来到这里为combination功能，ķ一套小号的结合 - 是ķ不同小号的元素的子集，注意顺序并不重要。

选择从n元素k元素等于选择从n - 1元素k - 1元素加上可供选择n - 1元素k元素。

enter image description here

使用此递归定义，我们可以这样写：

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

运算的问题是重复排列，其中有人已经给出答案。对于不重复的排列，请使用Data.List中的permutations。

来源

2014-03-22 11:44:56

列表的排列--Haskell

回答

相关问题