CODEWITHSUNDEEP
listhaskellcombinations
user5731286
user5731286

Reputation: 11

Combinations of k elements from set N haskell

I am trying to get all ordered combinations of 3 elements from a set of N: elements,that is : ["A","B","C","D"] --> ["ABC","ABD","ACD","BCD"].

I thought about writing something like [ x++y++z | pos(x)in list < pos(y) in list < pos(z) in list ]

How would i do that ?

Upvotes: 0

Views: 1245

Answers (2)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476729

You could write your function for three elements like using tails :: [a] -> [[a]]:

[x++y++z | (x:xs) <- tails list, (y:ys) <- tails xs, (z:_) <- tails ys]

This generates:

Prelude> :m Data.List
Prelude Data.List> (\list -> [x++y++z | (x:xs) <- tails list, (y:ys) <- tails xs, (z:_) <- tails ys]) ["A","B","C","D"]
["ABC","ABD","ACD","BCD"]

But usually you want a more scalable solution (one where you can generate combinations of k elements). You could for instance define a function combinations :: Int -> [a] -> [[a]] like:

combinations 0 _ = [[]]
combinations n ls = [ (x:ys) | (x:xs) <- tails ls, ys <- combinations (n-1) xs ]

and then you have to concat all the elements (for instance using a map).

Upvotes: 3

arrowd
arrowd

Reputation: 34401

There you go:

combinations 0 lst = [[]]
combinations k lst = do
    (x:xs) <- tails lst
    rest   <- combinations (n-1) xs
    return $ x : rest

Now, to get the result you want, use map concat (combinations 3 ["A","B","C","D"]).

Upvotes: 0

Related Questions