Ответ 1
Вы хотите replicateM:
replicateM :: Int -> m a -> m [a]
Определение так же просто, как:
replicateM n = sequence . replicate n
так что sequence в монаде списка, выполняющем здесь настоящую работу.
Перестановки списка - Haskell
Я хочу сделать все возможные комбинации подгрупп с 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]]
Ответы
Ответ 2
Для тех, кто пришел сюда для функции combination, 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' [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"]
Вопрос op - это повторные перестановки, которые кто-то уже дал ответ. Для не повторяющейся перестановки используйте permutations из Data.List.