Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Iterate over all pair combinations without repetition in Haskell

In haskell, given a list of elements, xs, the simplest way to iterate over all pair permutations with repetitions is:

[(x,y) | x <- xs, y <- xs]

I wish to be able to do the same, but only on combinations. If x and y were comparable, I could do

[(x,y) | x <- xs, y <- xs, x > y]

But I'd prefer a solution that is more generic and more efficient (I know that asympotitic complexity will remain squared, but we can halve actual runtime complexity by avoiding the usage of a filtering condition)

like image 319
tohava Avatar asked Jan 28 '15 11:01

tohava


2 Answers

What about:

[ (x,y) | (x:rest) <- tails xs , y <- rest ]
like image 132
chi Avatar answered Nov 07 '22 00:11

chi


If I copy and simplify Math.Combinat.Sets.choose for the particular case k=2, this gives

pairs :: [a] -> [[a]]
pairs []     = []
pairs (x:xs) = map (\y -> x:[y]) xs ++ pairs xs -- replace with \y -> (x,y) to get 2-tuples

>>> pairs [1,2,3]
[[1,2],[1,3],[2,3]]
like image 2
Stéphane Laurent Avatar answered Nov 07 '22 01:11

Stéphane Laurent