7

I need a function that does the same thing as itertools.combinations(iterable, r) in python

So far I came up with this:

{-| 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)

Is there a more elegant and efficient solution?

Chris Martin
  • 30,334
  • 10
  • 78
  • 137
Tobias Hermann
  • 9,936
  • 6
  • 61
  • 134

5 Answers5

12

xs elements taken n by n is

mapM (const xs) [1..n]

all combinations (n = 1, 2, ...) is

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

if you need without repetition

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

then

combinationsWRep xs n = filter ((n==).length.nub) $ mapM (const xs) [1..n]
josejuan
  • 9,338
  • 24
  • 31
  • 2
    Thanks, but that is not what I am looking for. `mapM (const "ABCD") [1..2]` returns `["AA","AB","AC","AD","BA","BB","BC","BD","CA","CB","CC","CD","DA","DB","DC","DD"]` not `["AB","AC","AD","BC","BD","CD"]` – Tobias Hermann Feb 14 '14 at 09:34
  • 1
    `filter ((2==).length.nub) $ mapM (const "ABCD") [1..2]` gives `["AB","AC","AD","BA","BC","BD","CA","CB","CD","DA","DB","DC"]`. ;-) – Tobias Hermann Feb 14 '14 at 09:52
6

(Based on @JoseJuan's answer)

You can also use a list comprehension to filter out those where the second character is not strictly smaller than the first:

[x| x <- mapM (const "ABCD") [1..2], head x < head (tail x) ]
Frank Schmitt
  • 30,195
  • 12
  • 73
  • 107
  • `head (tail x)` might be cleaner as `x !! 1` no? – daniel gratzer Feb 14 '14 at 14:47
  • 3
    @jozefg I think it's a matter of personal preference - you could even write x !! 0 < x !! 1. For me, coming from an imperative background, using x !! 1 implies that it's a O(1) operation, whereas for Haskell lists, it's O(n). head (tail x), on the other hand, clearly tells me that I'm performing two operations on a linked list. – Frank Schmitt Feb 14 '14 at 14:53
  • Correct me if i'm wrong, but that only works with length 2 strings. – dooderson May 04 '19 at 22:24
4

(Based on @FrankSchmitt’s answer)

We have map (const x) [1..n] == replicate n x so we could change his answer to 

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

And while in original question, 2 was a parameter k, for this particular example would probably not want to replicate with 2 and write

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

instead.

With a parameter k things are a bit more tricky if you want to generate them without duplicates. I’d do it recursively:

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

(This variant does not remove duplicates if there are already in the list as; if you worry about them, pass nub as to it)

Joachim Breitner
  • 25,395
  • 6
  • 78
  • 139
3

This SO answer:

subsequences of length n from list performance

is the fastest solution to the problem that I've seen.

Community
  • 1
  • 1
ErikR
  • 51,541
  • 9
  • 73
  • 124
1
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
  • 11
  • 1