Combinations with List.fold_left

[citromatik]

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;

[Christophe TROESTLER-4]

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

[Erick Matsen-2]

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:

>
>
> 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
>  
>

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

[Till Crueger-2]

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

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

This would do the trick:

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


------------------------------------

Archives up to December 31, 2008 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners/
The archives of the very official ocaml list (the seniors' one) can be found at http://caml.inria.fr
Attachments are banned and you're asked to be polite, avoid flames etc.Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/ocaml_beginners/

<*> Your email settings:
    Individual Email | Traditional

<*> To change settings online go to:
    http://groups.yahoo.com/group/ocaml_beginners/join
    (Yahoo! ID required)

<*> To change settings via email:
    mailto:ocaml_beginners-digest@...
    mailto:ocaml_beginners-fullfeatured@...

<*> To unsubscribe from this group, send an email to:
    ocaml_beginners-unsubscribe@...

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/