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)
What about:
[ (x,y) | (x:rest) <- tails xs , y <- rest ]
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]]
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With