リストの順列 - 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つの代わりに。引数として「ABC」を渡すの

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

結果：

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

定義がするのと同じくらい簡単です：それは、リスト上のsequenceだ

replicateM n = sequence . replicate n 

ここで本当の仕事をしているモナド。 combination機能のためにここに来た人のために

Answer 2

、セットのK -combination Sは、順序は重要ではありませんのでご注意、SのK異なる要素のサブセットです。

n要素からkの要素を選択してくださいn - 1要素からk - 1の要素を選択し、プラスn - 1要素からkの要素を選択してください等しいです。

この再帰的な定義を使用して、我々は書くことができます。

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

をオペアンプの質問は、誰かがすでに答えを与えている繰り返しの順列、です。反復されない順列の場合は、Data.Listのpermutationsを使用します。