获取列表中k个元素的所有可能组合

Question

我需要一个与python相同的功能itertools.combinations(iterable, r)

到目前为止,我想出了这个:

{-| forward application -}
x -: f = f x
infixl 0 -:

{-| combinations 2 "ABCD" = ["AB","AC","AD","BC","BD","CD"] -}
combinations :: Ord a => Int -> [a] -> [[a]]
combinations k l = (sequence . replicate k) l -: map sort -: sort -: nub
    -: filter (\l -> (length . nub) l == length l)

有更优雅和有效的解决方案吗？

Answer 1

xs采取n的元素n是

mapM (const xs) [1..n]

所有组合(n = 1,2,...)是

allCombs xs = [1..] >>= \n -> mapM (const xs) [1..n]

如果你需要不重复

filter ((n==).length.nub)

然后

combinationsWRep xs n = filter ((n==).length.nub) $ mapM (const xs) [1..n]

Answer 2

（基于@JoseJuan 的回答）

您还可以使用列表推导过滤掉第二个字符不严格小于第一个字符的那些：

[x| x <- mapM (const "ABCD") [1..2], head x < head (tail x) ]