Source code in the ocaml programming language

(* insert x at all positions into li and return the list of results *)
let rec insert x = function
  | [] -> [[x]]
  | a::m as li -> (x::li) :: (List.map (fun y -> a::y) (insert x m))

(* list of all permutations of li *)
let permutations li = 
  List.fold_right (fun a z -> List.concat (List.map (insert a) z)) li [[]]

(* convert a string to a char list *)
let chars_of_string s =
  let cl = ref [] in
  String.iter (fun c -> cl := c :: !cl) s;
  (List.rev !cl)

(* convert a char list to a string *)
let string_of_chars cl =
  String.concat "" (List.map (String.make 1) cl)


let deficient_perms = [
  "ABCD";"CABD";"ACDB";"DACB";
  "BCDA";"ACBD";"ADCB";"CDAB";
  "DABC";"BCAD";"CADB";"CDBA";
  "CBAD";"ABDC";"ADBC";"BDCA";
  "DCBA";"BACD";"BADC";"BDAC";
  "CBDA";"DBCA";"DCAB";
  ]

let it = chars_of_string (List.hd deficient_perms)

let perms = List.map string_of_chars (permutations it)

let results = List.filter (fun v -> not(List.mem v deficient_perms)) perms

let () = List.iter print_endline results


let array_of_perm s =
	let n = String.length s in
	Array.init n (fun i -> int_of_char s.[i] - 65);;
	
let perm_of_array a =
	let n = Array.length a in
	let s = String.create n in
	Array.iteri (fun i x ->
		s.[i] <- char_of_int (x + 65)
	) a;
	s;;

let find_missing v =
	let n = String.length (List.hd v) in
	let a = Array.make_matrix n n 0
	and r = ref v in
	List.iter (fun s ->
		let u = array_of_perm s in
		Array.iteri (fun i x -> x.(u.(i)) <- x.(u.(i)) + 1) a
	) v;
	let q = Array.make n 0 in
	Array.iteri (fun i x ->
		Array.iteri (fun j y ->
			if y mod 2 != 0 then q.(i) <- j
		) x
	) a;
	perm_of_array q;;

find_missing deficient_perms;;
(* - : string = "DBAC" *)