Loading ...
Sorry, an error occurred while loading the content.

Combinations with List.fold_left

Expand Messages
  • 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 =
    Message 1 of 4 , Oct 30, 2009
    • 0 Attachment
      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.
    • Christophe TROESTLER
      ... 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
      Message 2 of 4 , Oct 30, 2009
      • 0 Attachment
        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
        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 ... combo (List.flatten
        Message 3 of 4 , Oct 30, 2009
        • 0 Attachment
          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
          On Fri, 30 Oct 2009 18:14:20 +0100, citromatik ... This would do the trick: let combs elems = List.fold_right (fun heads tails -
          Message 4 of 4 , Oct 30, 2009
          • 0 Attachment
            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
          Your message has been successfully submitted and would be delivered to recipients shortly.