(* Method 3: Using approach 1 (04/12/2021) *)
(* To get the next permutation (e.g. of [0;1;3;6;5;4;2]), we need to: 
   1. Find the longest suffix that is decreasing (e.g. [6;5;4;2] and the rest are [0;1;3]).
   2. Find the element x just after this suffix (e.g. 3 in this case).
   3. Swap x with the element y just greater than it in the suffix (e.g. y = 4 and [6;5;3;2]).
   4. Reverse the suffix and append it to the modified prefix (e.g. [0;1;4] @ [2;3;5;6]).
*)

type 'a seq = Nil | Cons of 'a * (unit -> 'a seq);;

let rec to_list = function 
  Nil -> []
| Cons(x, xs) -> x::to_list (xs());;

let get_tail (Cons(_, xs)) = xs ();;

let rec get_sorted ls acc = match ls with
  [] -> acc, []
| [x] -> [x], []
| x::y::xs -> if x > y then x::acc, (y::xs)
              else get_sorted (y::xs) (x::acc);;

get_sorted (List.rev [0;1;3;9;8;7;2]) [];;

let find_just_greater ls x =
  List.fold_left min (max_int) (List.filter (fun y -> y > x) ls);;

let rec find_and_replace_just_greater ls x acc = match ls with
  [y] -> List.rev acc @ [x], y
| y::ys -> if y > x then List.rev acc @ x::ys, y
           else find_and_replace_just_greater ys x (y::acc);;

find_and_replace_just_greater [1;2;7;8;9] 3 [];;

let get_next perm = 
   let suf, p::pref = get_sorted (List.rev perm) [] in
   let new_suf, c = find_and_replace_just_greater (List.rev suf) p [] in
      List.rev pref @ c::new_suf;;

(* 
let perm = get_next [0;1;3;9;8;7;2];;
let perm = get_next perm;;
let perm = get_next perm;;
let perm = get_next perm;;
*) 

let rec is_last = function
  [x] -> true
| x::y::xs -> if x < y then false
              else is_last (y::xs);;

let rec get_permutations cur = 
   Cons(cur, fun () -> 
      if is_last cur then Nil
      else get_permutations (get_next cur));;


List.length (to_list (get_permutations [1;2;3;4])) = 24;;
List.length (to_list (get_permutations [1;2;3;4;5])) = 120;;

#trace get_permutations;;
let get_tail (Cons(_, xs)) = xs ();;
let a = get_permutations [1;2;3;4];;
let a = get_tail a;;
let a = get_tail a;;
let a = get_tail a;;
let a = get_tail a;;
