From: William James <w_a_x_man@...>
Date: 2006-08-03T01:25:12+09:00
Subject: For performance, write it in OCaml

Kristof Bastiaensen wrote:
> On Tue, 01 Aug 2006 17:48:41 +0900, Peter Hickman wrote:
>
> > The source code is available from
> > http://peterhi.dyndns.org/write_it_in_c/index.html
>
> Here is another version in Ruby.  It uses a more clever algorithm.
> It makes use of the fact that permuting the rows or the columns of
> a latin square still gives a latin square.  It also passes a constraint
> on the columns that the given number can be in, to reduce the backtracking
> even more.
>
> It runs in 15 seconds on my machine, which I find quite acceptable.
>
> I am sure that this algorithm coded in a compiled functional or logic
> language would be about as fast, or faster than your C code, but with the
> advantages of a higher level language.
>
> I still think you benchmark is flawed, because
>   1) the C program works only for squares of size 5
>   2) It shows totally no relevance to the kind of problems that you
>      would use Ruby for.  If you want raw speed for numerical applications,
>      then I would suggest to use a functional language (i.e. ocaml).

Here's an OCaml version that runs in about 1.5 seconds when
output is redirected to a file on my faster computer (3.2 GHz).
It uses the same algorithm as the C program.
The C version takes 1.961 seconds when writing to /dev/null on
the o.p.'s computer.  Since this is my first OCaml program, I'm
certain an expert could improve it.

(* compile with:
   ocamlopt -unsafe -inline 100 latin-squares.ml -o latin-squares.exe
*)

(* permutation code by Eric C. Cooper *)
let rec distribute elt = function
  | (hd :: tl) as list -> (elt :: list) ::
      (List.map (fun x -> hd :: x) (distribute elt tl))
  | [] -> [ [elt] ]
let rec permute = function
  | x :: rest -> List.flatten (List.map (distribute x) (permute rest))
  | [] -> [ [] ] ;;

let list =  [ 1; 2; 3; 4; 5 ]
let size = List.length list
let perms = permute list

let n = List.length perms
let incompat =  Array.make_matrix n n true ;;

for x = 0 to n - 1 do
  for y = 0 to n - 1 do
    incompat.(x).(y)  <-
      List.exists2 ( = ) (List.nth perms x) (List.nth perms y)
  done
done;;

let join list = String.concat "" (List.map string_of_int list)
let output_strings = List.map join perms ;;
let board = ( Array.make size 0 ) ;;

let rec add_a_row row =
  if row = size then
    print_endline
      ( String.concat ":"
        (List.map (fun i -> List.nth output_strings i)
          (Array.to_list board)) )
  else
    for latest = 0 to n - 1 do
      let prev_row = ref 0 in
      while (!prev_row < row) &&
            (not incompat.(latest).(board.(!prev_row))) do
        incr prev_row
      done;
      if !prev_row = row then
        ( board.(row) <- latest ; add_a_row (row + 1) )
    done
;;

add_a_row 0 ;;