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

Quick permutations

Okay, I've implemented permutations from SICP (Structure and
Interpretation of Computer Programs) (around p. 124):

define method permutations(s :: <list>) => (t :: <list>)
  if(empty?(s))
    list(#());
  else
    flatmap(method(x) map(curry(pair, x),
                          permutations(remove(s, x))) end, s);
  end if;
end method permutations;

where flatmap is:

define method flatmap(fn :: <function>, seq :: <sequence>) => (ans ::
<sequence>)
  reduce(concatenate, #(), map(fn, seq));
end method flatmap;

This works fine.  I just want it to be faster (the 40320 permutations of
a list of eight items takes some seconds to compute).  Is there an
implementation I'm overlooking that's quicker?

Sincerely,
Doug Auclair


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