William James wrote:
> 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.

An expert did suggest replacing a couple of lists with arrays.
This should be a bit faster.

(* 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 = Array.of_list (permute list)
let n = Array.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 ( = )  perms.(x) perms.(y)
  done
done;;

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

(* recursive function *)
let rec add_a_row row =
  if row = size then
    print_endline
      ( String.concat ":"
        (List.map (fun i ->  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 ;;