- Hi all,

I am trying to understand how to get all possible combinations of a list of

list:

# combs [['a';'b';'c'];['1';'2'];['Y';'Z']];;

char list list =

[['a';'1';'Y'];['a';'1';'Z'];['a';'2';'Y'];['a';'2';'Z'];['b';'1';'Y'];['b';'1';'Z'];['b';'2';'Y'];['b';'2';'Z']...]

Going step by step I end up with a solution for 2 lists:

# let combs3 l1 l2 =

List.fold_left (fun acc x -> (loop x l2)@acc) [] l1

# combs3 ['a';'b';'c'] ['1';'2';'3'];;

char list list = [['c'; '1']; ['c'; '2']; ['c'; '3']; ['b'; '1']; ['b';

'2']; ['b'; '3']; ['a'; '1']; ['a'; '2']; ['a'; '3']]

But I am not able to find a general solution for a list of list.

Could someone shed some light please? I am a bit frustrated with this...

Thanks in advance,

M;

--

View this message in context: http://old.nabble.com/Combinations-with-List.fold_left-tp26133783p26133783.html

Sent from the Ocaml Beginner mailing list archive at Nabble.com. - On Fri, 30 Oct 2009 10:14:20 -0700 (PDT), citromatik wrote:
>

Assume you have a function that does the job for a list with n

> But I am not able to find a general solution for a list of list.

> Could someone shed some light please? I am a bit frustrated with this...

elements (sublists) and write one (using the former) for a list with

n+1 elements. You can then turn this into a recursive function.

Oh, and sketch this on paper first.

Enjoy the problem !

ChriS - This is probably not the most efficient way, but this does what I think you

want to do:

let combo ll =

let rec aux accu = function

| h::t ->

combo

(List.flatten

(List.map (fun l -> List.map (fun x -> x::l) h) accu)) t

| [] -> accu

in

List.map List.rev (aux [[]] ll)

erick

On Fri, Oct 30, 2009 at 11:46 AM, Christophe TROESTLER <

Christophe.Troestler+ocaml@...<Christophe.Troestler%2Bocaml@...>> wrote:

[Non-text portions of this message have been removed]

>

>

> On Fri, 30 Oct 2009 10:14:20 -0700 (PDT), citromatik wrote:

> >

> > But I am not able to find a general solution for a list of list.

> > Could someone shed some light please? I am a bit frustrated with this...

>

> Assume you have a function that does the job for a list with n

> elements (sublists) and write one (using the former) for a list with

> n+1 elements. You can then turn this into a recursive function.

>

> Oh, and sketch this on paper first.

>

> Enjoy the problem !

> ChriS

>

>

- On Fri, 30 Oct 2009 18:14:20 +0100, citromatik <miguel.pignatelli@...>

wrote:

>

This would do the trick:

> Hi all,

>

> I am trying to understand how to get all possible combinations of a list

> of

> list:

let combs elems =

List.fold_right (fun heads tails ->

List.fold_right (fun head ress ->

(List.map (fun tail ->

head :: tail) tails) @ ress) heads []) elems [[]];;

It does get a bit ugly though....

HINT:

Try to make a function multiappend that gets a 'a list = heads and a 'a

list list = tails and returns all lists that result from appending each

head to each tail. For example

multiappend [1;2;3;4] [[1;2];[3;4]] =

[[1;1;2];[1;3;4];

[2;1;2];[2;3;4];

[3;1;2];[3;3;4];

[4;1;2];[4;3;4]]

Once you get this function done the rest will become more simple.

Hope this helps.

Till