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

Re: Quick permutations

Change list(#()) to #(), or if you need it to be mutable to make( <list>
). Maybe.

Change remove() to remove!(). See if any other methods have ! implimentations.

Change the if... to two methods and get clever with the method dispatch,
if possible:
define method permutations( s :: singleton( #() ) )
define method permutations( s :: <list> )

Change flatmap(method(x... to:
reduce( concatenate, #, map( method(x) map(curry(pair, x),
permutations(remove(s, x))) end, s ), seq );

Otherwise give x a type constraint in method(x).

I keep hearing Lispish voices in my head about map() but I don't know
what's best for a single collection in Dylan. Try to break down the task
to use for( x in seq ) rather than map. Maybe.

- Rob. 

dauclair@hotmail.com wrote:
> 
> 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/

-- 
Rob Myers - http://www.robmyers.org/   H2G2 - http://www.h2g2.com/
MacOS wonderfulness for The Hitch Hiker's Guide to the Galaxy Game.
"Smash Global Capitalism! Spend less money!"
Follow-Ups: References: