2012-01-08 68 views
16

我想使所有可能的子組與2個列表的組合。這裏,不只是這一個功能:列表的排列--Haskell

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

如果傳遞「ABC」這個功能,它返回:

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

同樣的方法的簡單修改可以返回的3所列出的組合而不是兩個。通過「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]] 
+5

您可以隨時嘗試使用hoogle:http://www.haskell.org/hoogle/?hoogle=Int+-%3E+[a]+-%3E+[[a]],它會將replicateM作爲第三個結果。 – sdcvvc 2012-01-08 18:00:34

+0

謝謝sdcvvc,我不知道有可能像這樣查詢hoogle! – RooSoft 2012-01-08 18:16:42

+2

從技術上講,這些是[置換](https://en.wikipedia.org/wiki/Permutation)不是[組合](https://en.wikipedia.org/wiki/Combination)。數學家將是迂腐的... – 2014-01-22 23:48:24

回答

27

你想要的是replicateM

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

的定義簡單:

replicateM n = sequence . replicate n 

所以它sequence名單monad在這裏做着真正的工作。

+1

這正是我尋找的那種渴望。非常感謝ehird! – RooSoft 2012-01-08 18:02:00

+0

@RooSoft你爲什麼期望更少?特別是在SO上。特別是[haskell]標籤(SO上最友好的標籤)。 – 2012-01-09 05:32:51

+0

你有多殘忍,讓我感到尷尬。這就是我所擁有的:'\ I l-> iterate(ap(fmap(:) l))[[]] !! i'T_T – Rotsor 2012-01-09 18:14:31

18

對於那些來到這裏爲combination功能,ķ一套小號的結合 - 是ķ不同小號的元素的子集,注意順序並不重要。

選擇從n元素k元素等於選擇從n - 1元素k - 1元素加上可供選擇n - 1元素k元素。

enter image description here

使用此遞歸定義,我們可以這樣寫:

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

運算的問題是重複排列,其中有人已經給出答案。對於不重複的排列,請使用Data.List中的permutations