From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id VAA07430; Sat, 23 Jun 2001 21:39:58 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id VAA07427 for <caml-list@pauillac.inria.fr>; Sat, 23 Jun 2001 21:39:57 +0200 (MET DST)
Received: from ux9.sp.cs.cmu.edu (UX9.SP.CS.CMU.EDU [128.2.220.166])
	by concorde.inria.fr (8.11.1/8.10.0) with SMTP id f5NJdtr04921
	for <caml-list@inria.fr>; Sat, 23 Jun 2001 21:39:56 +0200 (MET DST)
Received: from c198429-a.ross1.pa.home.com by ux9.sp.cs.cmu.edu id aa08565;
          23 Jun 2001 15:39 EDT
Message-ID: <3B34F067.CD965358@cmu.edu>
Date: Sat, 23 Jun 2001 15:39:19 -0400
From: "Eric C. Cooper" <ecc@cmu.edu>
X-Mailer: Mozilla 4.77 [en] (X11; U; Linux 2.2.19 i686)
X-Accept-Language: en
MIME-Version: 1.0
To: caml-list@inria.fr
Subject: Re: [Caml-list] New to OCaml: can someone explain how this code can be 
 done better?
References: <F13liS01qCcWNYgEj4v00003e3d@hotmail.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

(* Here is one approach to the problem.
   I think it is more natural to define permute on lists,
   and then write permute_string by converting to and from lists of
   characters.  As you'll see, the only imperative code is in this
   conversion step; the rest is purely functional.

   A simple recursive definition of permute is the following:
     The only permutation of an empty list is the empty list.
     Otherwise, the permutations of [x1;...;xN] are obtained by
     inserting x1 at all possible positions in each of
     the permutations of [x2;...;xN].

   We can translate this directly into ML: *)

    (* (distribute e [x1;...;xN]) returns the list
       [ [e;x1;...;xN]; [x1;e;x2;...;xN]; ...; [x1;...;xN;e] ] *)

    let rec distribute elt = function
      | (hd :: tl) as list ->
          (elt :: list) :: (List.map (fun x -> hd :: x) (distribute elt
tl))
      | [] -> [ [elt] ]

    (* (permute [x1;...;xN] returns the list of all permutations
       of [x1;...;xN] *)

    let rec permute = function
      | x :: rest -> List.flatten (List.map (distribute x) (permute
rest))
      | [] -> [ [] ]

(* Since we probably don't care about the order of the list of
   permutations, we can be slightly more efficient by defining a
   tail-recursive combination of flatten and map: *)

    (* (flat_rev_map f [x1;...;xN]) returns the list
       [rev (f xN) @ ... @ rev (f x1)] *)

    let flat_rev_map f list =
      let rec loop acc = function
        | x :: rest -> loop (List.rev_append (f x) acc) rest
        | [] -> acc
      in
      loop [] list

    let rec permute = function
      | x :: rest -> flat_rev_map (distribute x) (permute rest)
      | [] -> [ [] ]

(* Finally, we convert to and from strings using
   implode and explode functions: *)

    let explode string =
      let rec loop i acc =
        if i = 0 then acc
        else let i' = i-1 in loop i' (string.[i'] :: acc)
      in
      loop (String.length string) []

    let implode list =
      let string = String.create (List.length list) in
      let rec loop i = function
        | x :: rest -> string.[i] <- x; loop (i+1) rest
        | [] -> ()
      in
      loop 0 list;
      string

    let permute_string s =
      List.map implode (permute (explode s))

(* Eric Cooper, ecc@cmu.edu *)
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr