从列表中获取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)

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

- Tobias Hermann

---

请查看此答案。 - hammar

请访问以下链接查看与编程相关的内容：https://hoogle.haskell.org/?hoogle=%26 - pedrofurla

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]

- josejuan

---

谢谢，但那不是我要找的。mapM (const "ABCD") [1..2] 返回的是 ["AA","AB","AC","AD","BA","BB","BC","BD","CA","CB","CC","CD","DA","DB","DC","DD"] 而不是 ["AB","AC","AD","BC","BD","CD"]。 - Tobias Hermann

filter ((2==).length.nub) $ mapM (const "ABCD") [1..2] 的输出结果为 ["AB","AC","AD","BA","BC","BD","CA","CB","CD","DA","DB","DC"]。;-) - Tobias Hermann

Answer 2

（根据@JoseJuan的答案）

你也可以使用列表推导式来过滤掉第二个字符不严格小于第一个字符的情况：

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

- Frank Schmitt

---

head (tail x) 可以改写为 x !! 1，这样更简洁，不是吗？ - daniel gratzer

我认为这是个人偏好的问题 - 你甚至可以写 x !! 0 < x !! 1。对于我来说，来自命令式编程背景，使用 x !! 1 意味着它是一个 O(1) 操作，而对于 Haskell 列表来说，它是 O(n) 的。另一方面，head (tail x) 明确告诉我，我正在对链表执行两个操作。 - Frank Schmitt

请纠正我，但那只适用于长度为2的字符串。 - dooderson

Answer 3

（基于@FrankSchmitt的回答）

我们有map（const x）[1..n] == replicate n x，因此我们可以将他的答案更改为

[x| x <- sequence (replicate 2 "ABCD"), head x < head (tail x) ]

在原问题中，2是参数k，但对于这个特定的例子，可能不想用2来复制并编写代码。

[ [x1,x2] | x1 <- "ABCD", x2 <- "ABCD", x1 < x2 ]

有一个参数k，如果你想生成不重复的内容，就有点棘手了。我会用递归来实现:

代码示例：

f 0 _  = [[]]
f _ [] = []
f k as = [ x : xs | (x:as') <- tails as, xs <- f (k-1) as' ]

(如果已在列表as中，则此变体不会删除重复项； 如果您担心它们，请将nub as传递给它)

- Joachim Breitner

Answer 4

我见过的最快速解决这个问题的方案是这个 Stack Overflow 的回答：

subsequences of length n from list performance

- ErikR

Answer 5

compositions :: Int -> [a] -> [[a]]
compositions k xs
    | k > length xs = []
    | k <= 0        = [[]]
    | otherwise     = csWithoutHead ++ csWithHead
    where   csWithoutHead = compositions k $ tail xs
            csWithHead    = [ head xs : ys | ys <- compositions (k - 1) $ tail xs ]

- Mark