find the next greatest number, using list in OCaml

Question

Here is one interview question:

find the next greatest number that can be form by same digit of the given number ..

input: 4765, output: 5467

If using array, it is not that hard.

1. we transform the number to digit array.
2. we scan the array, record the latest (lowest position) digit (say as x) whose next neighbor is bigger
3. if the next neighbor is smaller (which means it is descending), then we record the smallest digit that bigger than x (say as y)
4. finally, we exchange x and y

However, in OCaml, if we use list, then I don't know how to do it. It seems the algorithm makes recursive hard.

Any suggestions?

Edit:

Please note I wish for a functional way (using list)

Edit

by follow @comingstorm's advices, I implemented like this:

exception NotFound;;


let rev_list_of_int n = 
  let rec process n = 
    let x = n / 10 and y = n mod 10 
    in 
    if x = 0 && y = 0 then []
    else 
      y::(process x)
  in 
  process n;;

let find_next_by_list n =
  let l = rev_list_of_int n
  in
  let rec find_x before_x x after_x = 
    match after_x with
    | [] | _::[] -> (before_x, -1, after_x)
    | hd1::hd2::tl -> 
      if hd1 > hd2 then (hd1::before_x, hd2, tl)
      else find_x (hd1::before_x) x (hd2::tl)
  in 
  let (bx, x, ax) = find_x [] (-1) l (* ax is rev *)
  in 
  if x = -1 then raise NotFound
  else 
    let rec find_y x path = function
    | [] -> raise NotFound
    | hd::tl -> 
      if hd > x then (path, hd, tl)
      else find_y x (hd::path) tl
    in 
    let (left, y, right) = find_y x [] (List.rev bx) (* left is rev, right is not  *)
    in 
    (* rev ax, then y, then right, then x, then rev left*)
    (List.rev_append (y::ax) right) @ (x::List.rev left)

Answer 1

For implementing this in a functional manner, it is more efficient to maintain your list of digits in reverse order -- so that the most rapidly changing digits are closer to the head of the list. This allows the implementation to avoid reallocating the entire list, improving the amortized performance.

Given a reverse list of digits (from least-significant to most-significant):

Starting at the least-significant digit (the head of the reversed list):
  look for the first digit smaller than its predecessor:  call it "a_k"
  save the list of digits after a_k as:  "unchanged"
Starting again at the least-significant digit:
  look for the first digit larger than a_k:  call it "a_l"
Accumulate the output list functional-style, starting with "unchanged":
  add a_l to the head of the list
  starting a third time at the least-significant digit:
    add each digit to the head of the output (reversing that portion of the list)
      stopping before a_l
    add a_k to the head of the output, instead of a_l
    after skipping a_l, continue to add digits from original to output
      stopping before a_k

In short: to do it functional-style, you must build the "modified" swap/reverse part of the list in place. You don't have to maintain your lists in least-significant-digit-first order (as assumed by the above pseudocode), but if you do, your next_permutation function will have amortized performance of O(1) in time and allocated memory.

[edit: correction, the O(1) performance is only if all digits are different...]

---

If you do want to maintain your digits in most-significant-digit-first order, you will still need to do a comparable scan and rebuild of the swap/reverse region, followed by an in-order copy of the unchanged region.

Answer 2

Simply generate the next permutation in lexicographic order:

Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
Swap a[k] with a[l].
Reverse the sequence from a[k + 1] up to and including the final element a[n].

found on wikipedia. An implementation in OCaml can be found here :

The following Ocaml code implements a variation on this algorithm (it returns the permutations of 1..n in reverse reverse-lexicographic order) :

(* exchange into l @ [x] @ accu x with the last element of l which is > x *)
let rec swap l x accu = match l with
| a::b::t when b > x -> a :: (swap (b::t) x accu)
| a::t -> (x::t) @ (a::accu)
| _ -> failwith "this can't happen"
;;

(* permut l m accu computes the permutation p' following p = rev(l)@m,
stores it into accu and recalls itself until p has no successor *)
let rec permut l m accu = match l,m with
| a::_, b::t when a > b -> let p = swap l b t in permut [] p (p::accu)
| _, b::t -> permut (b::l) t accu
| _, [] -> accu
;;

Answer 3

As Kwariz is pointing out (essentially), you can use the same solution with lists. The array solution can swap digits in constant time, but it still takes linear time to scan them all first. With a list of digits, you still have your linear scan, plus a linear operation to swap digits.

It might be possible to come up with a prettier recursive solution. The problem is that you're working with a fairly "global" property of the list. It's not easy to break it into the usual recursive pieces. But it's not too far off. For one thing, if you can perform your operation on the tail of the list, then this is also the correct result for the whole list (with head added back on).