Combinatorics in a functional way

Combinatorics in a functional way

[Erik de Castro Lopo]

Hi all,

I'm currently working on something where I need to to generate a
set of permutations that fit a set of rules. Currently I am doing
something like:

    let find_combi p0 p1 =
        let out = ref [] in
	for i0 = 1 to p0 do
            for i1 = 1 to p0 do
                for i2 = 1 to p0 do
                    for i3 = 1 to p1 do
                        for i4 = 1 to p1 do
                            for i5 = 1 to p1 do
                                for i6 = 1 to p1 do
                                    for i7 = 1 to p1 do
                                        if test_combi i0 i1 i2 i3 i4 i5 i6 i7 then
                                            lst := (i0, i1, i2, i3, i4, i5, i6, i7) :: lst
                                    done ;
                                done ;
                            done ;
                        done ;
                    done ;
                done ;
            done ;
        done ;
        !lst

This works, but I find it excessively ugly. It feels like I'm coding
in C again!

Can anyone come up with a cleaner, more functional way of solving 
problems like this? I'm thinking that something like lazy lists
might be a solution.

Any tips appreciated.

Cheers,
Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo
+-----------------------------------------------------------+
Microsoft VISTA : Virus Infection Spyware Trojans and Adware!

Re: [Caml-list] Combinatorics in a functional way

[David Baelde]

Hi,

Here's a possibility. It certainly feels more functional, and also
consumes less memory, but I'm not sure that it fits your needs.
Basically the idea is to build an iterator over permutations, using a
function computing the next permutation from a given one -- this is
basically incrementing a list of digits seen as a number.

I'm lazy so I didn't pass min/max as parameters everywhere. My
solution doesn't use different upper bounds for digits like you (p0
for i0 to i2; p1 for i3 to i7) but it could be adapted.

let min = 2
let max = 4

exception Last

let rec init n = if n=0 then [] else min::(init (n-1))

let rec next acc = function
  | [] -> raise Last
  | x::l ->
      if x<max then List.rev_append acc ((x+1)::l) else next (min::acc) l

(* Iterates [f] over all lists of [len] digits between [min] and [max]. *)
let iter_combi len f =
  let rec iter cur =
    f cur ;
    iter (next [] cur)
  in
    try iter (init len) with Last -> ()

let _ =
  iter_combi 3
    (fun c ->
       print_string (String.concat " " (List.map string_of_int c)) ;
       print_newline ())

By the way, I started using this thing when coding in C to avoid the
memory cost of generating the list of permutations, not because it
felt more functional.

Hope that helps.
-- 
David

Re: [Caml-list] Combinatorics in a functional way

[Pietro Abate]

On Wed, Feb 21, 2007 at 08:36:03PM +1100, Erik de Castro Lopo wrote:
> I'm currently working on something where I need to to generate a
> set of permutations that fit a set of rules. Currently I am doing
> something like:

I'm not sure this is exactly what you want... but I think it's a good
starting point to look at for this kind of problems. Making it lazy is
just a matter of changing the definition of the modules Seq.

module Seq =
    struct
        let mzero = []
        let return a = [a]
        let bind m f = List.flatten (List.map f m)
        let mplus = List.append
        let guard b = if b then return () else mzero
    end
        ;;

let range n =
  let rec aux i l =
      if i = 0 then l else i::(aux (i-1) l)
  in List.rev ( aux n [] )
;;

let test _ _ _ = true ;;

let find_comb p0 p1 =
    Seq.bind (range p0) (fun i0 ->
        Seq.bind (range p0) (fun i1 ->
            Seq.bind (range p1) (fun i2 ->
                Seq.bind (Seq.guard (test i0 i1 i2)) (fun _ ->
                    Seq.return (i0,i1,i2)
                )
            )
        )
    )
;;

# let a = find_comb 4 2 ;;
val a : (int * int * int) list =
  [(1, 1, 1); (1, 1, 2); (1, 2, 1); (1, 2, 2); (1, 3, 1); (1, 3, 2);
   (1, 4, 1); (1, 4, 2); (2, 1, 1); (2, 1, 2); (2, 2, 1); (2, 2, 2);
   (2, 3, 1); (2, 3, 2); (2, 4, 1); (2, 4, 2); (3, 1, 1); (3, 1, 2);
   (3, 2, 1); (3, 2, 2); (3, 3, 1); (3, 3, 2); (3, 4, 1); (3, 4, 2);
   (4, 1, 1); (4, 1, 2); (4, 2, 1); (4, 2, 2); (4, 3, 1); (4, 3, 2);
   (4, 4, 1); (4, 4, 2)]
#

pietro

-- 
++ Blog: http://blog.rsise.anu.edu.au/?q=pietro
++ 
++ "All great truths begin as blasphemies." -George Bernard Shaw
++ Please avoid sending me Word or PowerPoint attachments.
   See http://www.fsf.org/philosophy/no-word-attachments.html

Re: [Caml-list] Combinatorics in a functional way

[Nicolas Pouillard]

On 2/21/07, Erik de Castro Lopo <mle+ocaml@mega-nerd.com> wrote:
> Hi all,

Hi,

[...]

>
> Can anyone come up with a cleaner, more functional way of solving
> problems like this? I'm thinking that something like lazy lists
> might be a solution.
>

I need it some days ago and came to two different solutions.

In my case I needed to iterate over list permutations.

So in your case just use a function like range:

let range n =
 let rec aux i l =
     if i = 0 then l else i::(aux (i-1) l)
 in List.rev ( aux n [] )
;;

1/ The first is short but consume memory:

let fold = List.fold_right;;

let cartesian_product llz =
  fold begin fun ly llx ->
    fold begin fun y acc ->
      fold begin fun lx acc ->
        (y :: lx) :: acc
      end llx acc
    end ly []
  end llz [[]]
;;

cartesian_product [range p0; range p1; range p2];;

2/ This one consider list given as input like a counting base
(decimal, hexadecimal...).

type 'a enum = Stop | Elt of (('a list) * (unit -> 'a enum))

let enum_cartesian_product ll =
  let dupl l =
    List.rev_map begin fun x ->
      if x = [] then invalid_arg "enum_cartesian_product: empty list";
      (x, x)
    end l in
  let rec wrap_result res =
    let element = List.map (fun (x, _) -> List.hd x) res
    and kont () = increment (List.rev res) true []
    in (element, kont)
  and increment revll ret res =
    match revll with
    | [] ->
        if ret then (* it is the real end of the stream *) Stop
        else (* that's a element of stream *) Elt(wrap_result res)
    | (l, init) :: rest ->
        if ret then begin
          match l with
          | [] -> assert false
          | [ v ] -> increment rest true ((init, init) :: res)
          | v :: other -> increment rest false ((other, init) :: res)
        end else increment rest false ((l, init) :: res)
  in Elt(wrap_result (dupl ll))

let rec iter f =
  function
  | Elt(v, kont) -> f v; iter f (kont ())
  | Stop -> ()
;;

let e = enum_cartesian_product [range p0; range p1; range p2]
in
iter begin fun combi ->
  print_endline (String.concat "; " (List.map string_of_int combi))
end e;;

Hope that helps,

-- 
Nicolas Pouillard

Re: [Caml-list] Combinatorics in a functional way

[Frédéric van der Plancke]

David Baelde wrote:
> Hi,
>
> Here's a possibility. It certainly feels more functional, and also
> consumes less memory, but I'm not sure that it fits your needs.
> Basically the idea is to build an iterator over permutations, using a
> function computing the next permutation from a given one -- this is
> basically incrementing a list of digits seen as a number.
>
> I'm lazy so I didn't pass min/max as parameters everywhere. My
> solution doesn't use different upper bounds for digits like you (p0
> for i0 to i2; p1 for i3 to i7) but it could be adapted.
>
> let min = 2
> let max = 4
>
> exception Last
>
> let rec init n = if n=0 then [] else min::(init (n-1))
>
> let rec next acc = function
>  | [] -> raise Last
>  | x::l ->
>      if x<max then List.rev_append acc ((x+1)::l) else next (min::acc) l
>
> (* Iterates [f] over all lists of [len] digits between [min] and 
> [max]. *)
> let iter_combi len f =
>  let rec iter cur =
>    f cur ;
>    iter (next [] cur)
>  in
>    try iter (init len) with Last -> ()

You can also define iter_combi recursively in terms of itself:

(* Iterates [f] over all lists of [len] digits between [min] and [max]. *)
let rec iter_combi min max len f =
    assert (len >= 0);
    if len = 0 then (f [])
    else iter_combi min max (len - 1) (fun tail ->
        for x = min to max do
            f (x :: tail)
        done)

(if you want the lists be passed to f in lexicographical order, write f 
(List.rev (x::tail)) instead of f(x::tail).)

Frédéric
>
> let _ =
>  iter_combi 3
>    (fun c ->
>       print_string (String.concat " " (List.map string_of_int c)) ;
>       print_newline ())
>
> By the way, I started using this thing when coding in C to avoid the
> memory cost of generating the list of permutations, not because it
> felt more functional.
>
> Hope that helps.

Re: [Caml-list] Combinatorics in a functional way

[Gabriel Kerneis]

[-- Attachment #1: Type: text/plain, Size: 451 bytes --]

Le Wed, 21 Feb 2007 12:29:06 +0100, "Nicolas Pouillard"
<nicolas.pouillard@gmail.com> a écrit :
> So in your case just use a function like range:
> 
> let range n =
>  let rec aux i l =
>      if i = 0 then l else i::(aux (i-1) l)
>  in List.rev ( aux n [] )
> ;;

I'd rather use the tail recursive version :

let range n =
  let rec aux i l =
      if i = 0 then l else aux (i-1) (i::l)
  in aux n []
 ;;


-- 
Gabriel Kerneis


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] Combinatorics in a functional way

[Jacques Carette]

And with the Seq module (left at end), combined with the pa_monad 
extention, one can rewrite find_comb as

let find_comb p0 p1 =
  perform with Seq in
    i0 <-- range p0;
    i1 <-- range p0;
    i2 <-- range p1;
    guard (test i0 i1 i2);
    return (i0, i1, i2)

I do believe that is more readable :-)

Jacques

Pietro Abate wrote:
> I'm not sure this is exactly what you want... but I think it's a good
> starting point to look at for this kind of problems. Making it lazy is
> just a matter of changing the definition of the modules Seq.
>
> module Seq =
>     struct
>         let mzero = []
>         let return a = [a]
>         let bind m f = List.flatten (List.map f m)
>         let mplus = List.append
>         let guard b = if b then return () else mzero
>     end
>         ;;
>
> let range n =
>   let rec aux i l =
>       if i = 0 then l else i::(aux (i-1) l)
>   in List.rev ( aux n [] )
> ;;
>
> let test _ _ _ = true ;;
>
> let find_comb p0 p1 =
>     Seq.bind (range p0) (fun i0 ->
>         Seq.bind (range p0) (fun i1 ->
>             Seq.bind (range p1) (fun i2 ->
>                 Seq.bind (Seq.guard (test i0 i1 i2)) (fun _ ->
>                     Seq.return (i0,i1,i2)
>                 )
>             )
>         )
>     )
> ;;
>
>   

Re: [Caml-list] Combinatorics in a functional way

[Fernando Alegre]

Hi,

This is what I would do:

let get i (i0,i1,i2,i3,i4,i5,i6,i7) = match i with
  | 0 -> i0 | 1 -> i1 | 2 -> i2 | 3 -> i3 | 4 -> i4 | 5 -> i5 | 6 -> i6
  | 7 -> i7 | _ -> invalid_arg "get"

let set i (i0,i1,i2,i3,i4,i5,i6,i7) x = match i with
  | 0 -> (x,i1,i2,i3,i4,i5,i6,i7) | 1 -> (i0,x,i2,i3,i4,i5,i6,i7)
  | 2 -> (i0,i1,x,i3,i4,i5,i6,i7) | 3 -> (i0,i1,i2,x,i4,i5,i6,i7)
  | 4 -> (i0,i1,i2,i3,x,i5,i6,i7) | 5 -> (i0,i1,i2,i3,i4,x,i6,i7)
  | 6 -> (i0,i1,i2,i3,i4,i5,x,i7) | 7 -> (i0,i1,i2,i3,i4,i5,i6,x)
  | _ -> invalid_arg "set"

let next bounds index =
  let rec loop i index =
    if i = 8 then index else
      let x = get i index in
        if x < get i bounds then set i index (x+1)
        else loop (i+1) (set i index 0)
  in
    loop 0 index

let fold f acc bounds =
  let rec next i index =
    if i = 7 then index
    else if index < get i bounds then set i (index+1)
    else next (i+1) (set i index 0)
  and loop a index =
    if i = 8 then acc else loop (f a index) (next bounds index)
  in
    loop 0 (0,0,0,0,0,0,0)

let find_combi ((p0,p1,p2,p3,p4,p5,p6,p7) as bounds) =
  fold (fun l x -> x :: l) [] bounds

Fernando

On Wed, Feb 21, 2007 at 08:36:03PM +1100, Erik de Castro Lopo wrote:
> Hi all,
> 
> I'm currently working on something where I need to to generate a
> set of permutations that fit a set of rules. Currently I am doing
> something like:

Re: [Caml-list] Combinatorics in a functional way

[Brian Hurt]

A good, functional, generic solution:

type 'a queue = 'a list * 'a list;;

let init lst : 'a queue = lst, [];;

let is_empty : 'a queue -> bool = function
    | [], [] -> true
    | _ -> false
;;

let rem_head : 'a queue -> 'a * 'a queue = function
    | (h::t), b -> h, (t, b)
    | [], b ->
        match (List.rev b) with
        | h :: t -> h, (t, [])
        | [] -> invalid_arg "rem_head on empty queue!"
;;

let append_tail ((s, b) : 'a queue) x : 'a queue = s, (x :: b);;

let fold_permute_list f accum lst =
    let rec loop1 acc t q n =
        if is_empty q then
            f acc (List.rev t)
        else
            let rec loop2 acc q i =
                if i == 0 then
                    acc
                else
                    let h, q = rem_head q in
                    let acc = loop1 acc (h :: t) q (n-1) in
                    loop2 acc (append_tail q h) (i-1)
            in
            loop2 acc q n
    in
    loop1 accum [] (init lst) (List.length lst)
;;

Okasaki should be required reading.

Brian

Re: [Caml-list] Combinatorics in a functional way

[Erik de Castro Lopo]

Brian Hurt wrote:

> A good, functional, generic solution:

Thanks all.

There's a whole bunch of really good suggestions there. Its going 
to take me a while to digest all this and decide which technique 
best fits my problem.

> Okasaki should be required reading.

Indeed.

Cheers,
Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo
+-----------------------------------------------------------+
"Do I do everything in C++ and teach a course in advanced swearing?"
-- David Beazley at IPC8, on choosing a language for teaching