Find the missing permutation: Difference between revisions

Alternate method : if we had all permutations, each letter would appear an even number of times at each position.

Since there is only one permutation missing, we can find where each letter goes by looking at the parity of

the number of occurences of each letter.

<lang ocaml>let array_of_perm s =

let n = String.length s in

let a = Array.make n 0 in

for i=0 to n-1 do

a.(i) <- (int_of_char s.[i]) - 65

done;

a;;

let perm_of_array a =

let n = Array.length a in

let s = String.make n ' ' in

for i=0 to n-1 do

s.[i] <- char_of_int (a.(i) + 65)

done;

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

let rec aux = function

[ ] -> () | s::w ->

let u = ints_of_perm s in

for i=0 to n-1 do a.(i).(u.(i)) <- a.(i).(u.(i)) + 1 done;

aux w

in

aux v;

let q = Array.make n 0 in

for i=0 to n-1 do

for j=0 to n-1 do

if a.(i).(j) mod 2 != 0 then q.(i) <- j

done

done;

perm_of_array q;;

find_missing deficient_perms;;

(* - : string = "DBAC" *)</lang>