Các danh tiếng của một danh sách - Haskell

Question

Tôi muốn kết hợp tất cả các nhóm con có thể với 2 danh sách. Đây là một chức năng mà chỉ này:

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

Nếu bạn vượt qua "abc" để chức năng này, nó sẽ trả về này:

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

Một thay đổi đơn giản trong những phương pháp tương tự có thể trở lại sự kết hợp của 3 liệt kê thay vì hai.

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

Kết quả đi "abc" như một cuộc tranh cãi:

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

cách đơn giản nhất để làm cho nó mở rộng đến một số tùy ý của danh sách là gì? Đây là những gì khai báo kiểu nên hình như:

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

Answer 1

gì bạn muốn là replicateM:

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

Định nghĩa được đơn giản như:

replicateM n = sequence . replicate n 

vì vậy nó sequence trong danh sách monad đang làm công việc thực sự ở đây.

Answer 2

Đối với những người đến đây cho combination chức năng, một k -combination của một tập S là một tập hợp con của k yếu tố riêng biệt của S, lưu ý rằng thứ tự không quan trọng.

Chọn k yếu tố từ n yếu tố bằng với chọn k - 1 yếu tố từ n - 1 yếu tố cộng với chọn k yếu tố từ n - 1 yếu tố.

Sử dụng định nghĩa đệ quy này, chúng ta có thể viết: Câu hỏi

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

của op là một hoán vị lặp đi lặp lại, mà ai đó đã đưa ra một câu trả lời. Đối với hoán vị không lặp lại, hãy sử dụng permutations từ Data.List.