Combinations

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Combinations

sinosoidal
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
Reply | Threaded
Open this post in threaded view
|

Re: Combinations

Bernd Holzmüller
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
Reply | Threaded
Open this post in threaded view
|

Re: Combinations

Henning Thielemann
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
Reply | Threaded
Open this post in threaded view
|

Re: Combinations

Lennart Augustsson
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
Reply | Threaded
Open this post in threaded view
|

Re: Combinations

Mirko Rahn
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
Reply | Threaded
Open this post in threaded view
|

Re: Combinations

Udo Stenzel
In reply to this post by sinosoidal
[hidden email] wrote:
> 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]]

sequence

Finding out why it is named that strangely is left as an excercise.  :-)


Udo.
--
The future isn't what it used to be.  (It never was.)

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

signature.asc (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Combinations

Henning Thielemann

On Tue, 6 Jun 2006, Udo Stenzel wrote:

> [hidden email] wrote:
>> 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]]
>
> sequence


I see, it is just
    sequence  ==  foldr (liftM2 (:)) (return [])
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe