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
Весьма императивное решение, с использованием ссылок.

Aucun commentaire:

Publier un commentaire