Skip to content

Instantly share code, notes, and snippets.

@MassD
Last active November 26, 2023 23:09
Show Gist options
  • Save MassD/be3f6571967662b9d3c6 to your computer and use it in GitHub Desktop.
Save MassD/be3f6571967662b9d3c6 to your computer and use it in GitHub Desktop.
A permutation generator with Johnson Trotter algorithm
type direction = L | R
let attach_direction a = Array.map (fun x -> (x, L)) a
let swap a i j = let tmp = a.(j) in a.(j) <- a.(i); a.(i) <- tmp
let is_movable a i =
let x,d = a.(i) in
match d with
| L -> if i > 0 && x > (fst a.(i-1)) then true else false
| R -> if i < Array.length a - 1 && x > (fst a.(i+1)) then true else false
let move a i =
let x,d = a.(i) in
if is_movable a i then
match d with
| L -> swap a i (i-1)
| R -> swap a i (i+1)
else
failwith "not movable"
let scan_movable_largest a =
let rec aux acc i =
if i >= Array.length a then acc
else if not (is_movable a i) then aux acc (i+1)
else
let x,_ = a.(i) in
match acc with
| None -> aux (Some i) (i+1)
| Some j -> aux (if x < fst(a.(j)) then acc else Some i) (i+1)
in
aux None 0
let flip = function | L -> R | R -> L
let scan_flip_larger x a =
Array.iteri (fun i (y, d) -> if y > x then a.(i) <- y,flip d) a
let permutations_generator l =
let a = Array.of_list l |> attach_direction in
let r = ref (Some l) in
let next () =
let p = !r in
(match scan_movable_largest a with
| None -> r := None
| Some i ->
let x, _ = a.(i) in (
move a i;
scan_flip_larger x a;
r := Some (Array.map fst a |> Array.to_list)));
p
in
next
(* example *)
let generator = permutations_generator [1;2;3]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment