[Prev][Next][Index][Thread]

Re: Quick permutations, another entry


> This runs in under 0.5 seconds on a 450Mhz, Pentium III.  If anyone
> wants to improve the code, please go ahead.

Yours certainly runs quickly!  Another entry comes from jt (jan) that
also runs in less than 0.5 seconds and entirely side-steps the
memory-management problem by only retaining the current permutation
(which it shares out to the world via a function):


define constant $permuted-vector-size = 8;
define variable *permutation* = make(<vector>, size: 8);

define class <position> (<object>)
  slot available? :: <boolean> = #t, init-keyword: available?:;
  slot value, init-keyword: value:;
end class;

define constant <permuted-vector> = limited(<vector>, of: <position>);
define variable *taken* :: <permuted-vector> =
    make(<permuted-vector>, size: 8, fill: make(<position>));

define macro with-available-position
 { with-available-position(?position:variable = ?x:expression) ?:body
end
 } => {
   if(?x.available?)
     ?x.available? := #f;
     let ?position = ?x.value;
     ?body;
     ?x.available? := #t;
   end if;
 }
end macro;

define method permute(permuted-fill-pointer :: <integer>,
    f :: <function>)
  if (permuted-fill-pointer == $permuted-vector-size) // permutation
complete
    f(*permutation*);
  else
    for(pos from 0 below $permuted-vector-size)
      with-available-position(item = *taken*[pos])
        *permutation*[permuted-fill-pointer] := item;
        permute(permuted-fill-pointer + 1, f);
      end;
    end for;
  end if;
end method permute;

define method init-taken()
  for(x from 1 to 8)
    *taken*[x - 1] := make(<position>, value: x);
  end;
end method;

define method permute-example()
  init-taken();
  let (seconds, milliseconds) = timing ()
                                  permute(0, curry(format-out, "%=\n"));
                                end;
  format-out("%d seconds %d milliseconds\n", seconds, milliseconds);
end method;



Sent via Deja.com
http://www.deja.com/
Follow-Ups: References: