Find the missing permutation: Difference between revisions

Content added Content deleted
(→‎{{header|OCaml}}: alternate method)
Line 610: Line 610:
Alternate method : if we had all permutations, each letter would appear an even number of times at each position.
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
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.
the number of occurences of each letter. The following program works with permutations of at least 3 letters.
<lang ocaml>let array_of_perm s =
<lang ocaml>let array_of_perm s =
let n = String.length s in
let n = String.length s in
Line 633: Line 633:
let rec aux = function
let rec aux = function
[ ] -> () | s::w ->
[ ] -> () | s::w ->
let u = ints_of_perm s in
let u = array_of_perm s in
for i=0 to n-1 do a.(i).(u.(i)) <- a.(i).(u.(i)) + 1 done;
for i=0 to n-1 do a.(i).(u.(i)) <- a.(i).(u.(i)) + 1 done;
aux w
aux w
Retrieved from "https://rosettacode.org/wiki/Find_the_missing_permutation"