列表的排列 - Haskell

Question

我想制作具有2个列表的子组的所有可能组合.这是一个执行此操作的函数:

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

如果将"abc"传递给此函数,则返回以下内容:

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

对同一方法的简单修改可以返回3个列表而不是2个列表的组合.

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

传递"abc"作为参数的结果:

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

Answer 1

你想要的是replicateM:

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

定义很简单:

replicateM n = sequence . replicate n

所以它sequence在列表monad上正在做真正的工作.

Answer 2

对于那些来到这里的组合功能,ķ一套结合- 小号的一个子集ķ的不同元素的小号,注意顺序并不重要.

选择k从元素n的元素等于选择k - 1从元素n - 1的元素加选择k的元素n - 1的元素.

使用这个递归定义,我们可以写:

combinations :: Int -> [a] -> [[a]]
combinations k xs = combinations' (length xs) k xs
  where combinations' n k' l@(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"]

该问题是一个重复的排列,有人已经给出了答案.对于非重复排列,请使用permutationsData.List.