# Combinations

7 messages
Open this post in threaded view
|

## Combinations

 Hi, I need a functions which takes as argument a list of lists like this one: [[1,2],[3],[4]] and gives me a list of list with all the possible combinations like this one: [[1,3,4],[2,3,4]] In this case there are only 2 combinations but if there was more than one element in the other lists the results were much more. I'm a little stuck in this simple problem. First i was thinking in cartesian product but then i realized that i may not be what i really need. Any tip? Many thx, Nuno Santos _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Combinations

 This should do: combinations :: [[a]] -> [[a]] combinations [] = [[]] combinations [[x]] = [[x]] combinations ([] : xxs) = combinations xxs combinations ((h : tl) : xxs) = [h : r | r <- combinations xxs] ++                 if null tl then [] else combinations (tl : xxs) Bernd [hidden email] schrieb: > Hi, > > I need a functions which takes as argument a list of lists like this one: > > [[1,2],[3],[4]] > > and gives me a list of list with all the possible combinations like this one: > > [[1,3,4],[2,3,4]] > > In this case there are only 2 combinations but if there was more than one > element in the other lists the results were much more. > > I'm a little stuck in this simple problem. > > First i was thinking in cartesian product but then i realized that i may > not be what i really need. > > Any tip? > > Many thx, > > Nuno Santos > > _______________________________________________ > Haskell-Cafe mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/haskell-cafe>   -- Bernd Holzmüller Dipl.-Inf. ICS AG Sonnenbergstraße 13 D-70184 Stuttgart Tel.: +49 (0) 711 / 2 10 37 - 643 Fax:  +49 (0) 711 / 2 10 37 - 653 Mobile: +49 (0) 151 / 17449 534 mailto:[hidden email] www.ics-ag.de _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Combinations

 In reply to this post by sinosoidal On Tue, 6 Jun 2006 [hidden email] wrote: > Hi, > > I need a functions which takes as argument a list of lists like this one: > > [[1,2],[3],[4]] > > and gives me a list of list with all the possible combinations like this one: > > [[1,3,4],[2,3,4]] > > In this case there are only 2 combinations but if there was more than one > element in the other lists the results were much more. Using the List instance of monads you can simplify things.   foldr (Monad.liftM2 (:)) [[]] [[1,2],[3],[4]] > I'm a little stuck in this simple problem. > > First i was thinking in cartesian product but then i realized that i may > not be what i really need. cartesian product can be computed by   liftM2 (,) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Combinations

 In reply to this post by sinosoidal Sounds like cartesian product to me. So you could try combinations [] = [[]] combinations (xs:xss) = liftM2 (:) xs (combinations xss)         -- Lennart [hidden email] wrote: > Hi, > > I need a functions which takes as argument a list of lists like this one: > > [[1,2],[3],[4]] > > and gives me a list of list with all the possible combinations like this one: > > [[1,3,4],[2,3,4]] > > In this case there are only 2 combinations but if there was more than one > element in the other lists the results were much more. > > I'm a little stuck in this simple problem. > > First i was thinking in cartesian product but then i realized that i may > not be what i really need. > > Any tip? > > Many thx, > > Nuno Santos > > _______________________________________________ > Haskell-Cafe mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/haskell-cafe> _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Combinations

 Henning Thielemann wrote:  > combinations = foldr (Monad.liftM2 (:)) [[]] Lennart Augustsson wrote: > combinations [] = [[]] > combinations (xs:xss) = liftM2 (:) xs (combinations xss) List comprehension is faster when compiled with ghc-6.4.2 -O: combinations [] = [[]] combinations (xs:xss) = [ x:y | x <- xs, y <- combinations xss ] BTW, I think 'cross_many' would be a better name. -- -- Mirko Rahn -- Tel +49-721 608 7504 -- --- http://liinwww.ira.uka.de/~rahn/ --- _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe