Permutations of a list - Haskell

Question

I want to make all possible combinations of subgroups with 2 lists. Here is a function that does just this:

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

If you pass "abc" to this function, it returns this:

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

A simple modification of the same method could return combinations of 3 lists instead of two.

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

Result of passing "abc" as an argument:

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

What's the simplest way to make it scale to an arbitrary number of lists? Here is what the type declaration should look like:

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

Answer 1

For those come here for the combination function, a k-combination of a set S is a subset of k distinct elements of S, note that the order doesn't matter.

Choose k elements from n elements equals choose k - 1 elements from n - 1 elements plus choose k elements from n - 1 elements.

Use this recursive definition, we can write:

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

The op's question is a repeated permutations, which someone has already given an answer. For non-repeated permutation, use permutations from Data.List.

Answer 2

What you want is replicateM:

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

The definition is as simple as:

replicateM n = sequence . replicate n

so it's sequence on the list monad that's doing the real work here.