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