## dimanche 18 avril 2010

### Project Euler #24

(* swaps elements of indexes i and j in array a*)
let swap a i j =
let t = a.(i) in
a.(i) <- a.(j); a.(j) <- t;;

(* reverses part of array a from index i to the end of array*)
let reverse a i =
let l = (Array.length a) - 1 in
for k = 0 to (l - i)/2 do
swap a (i + k) (l - k)
done;;

(* generates next permutation of array *)
let make_next_permutation a =
let j = ref 0 in
let l = ref 0 in
for i = 0 to (Array.length a) - 2 do
if a.(i) < a.(i+1) then
j.contents <- i
done;
for i = 0 to (Array.length a) - 1 do
if a.(!j) < a.(i) then
l.contents <- i
done;
swap a !j !l;
reverse a (!j+1);;

let make_permutations a =
let t = ref 1 in
while !t < 1000000 do
make_next_permutation a;
t := (!t + 1);
done;;

let t = [| 0; 1; 2; 3; 4; 5; 6; 7; 8; 9 |];;
make_permutations t;;
Array.iter (Printf.printf "%d") t;;
Printf.printf "\n";;


http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations
Весьма императивное решение, с использованием ссылок.