Перестановки списка - 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 списков вместо двух.

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 в монаде списка, которая делает настоящую работу здесь.

Answer 2

Для тех, кто пришел сюда для функции комбинация , комбинация k из набора S является подмножеством k отдельные элементы S , обратите внимание, что порядок не имеет значения.

Выберите 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"]

Вопрос опера - повторные перестановки, на которые кто-то уже дал ответ. Для неповторяющихся перестановок используйте permutations из Data.List.