Hrmm, I suppose you're right. I was thinking that we could magically write permute so that it wound up with n! thunks in an array, and then grab the nth element in constant time. I guess that's not very correct. And by "not very" I mean "not even close to". 

On Thu, Feb 12, 2009 at 1:33 PM, Brent Yorgey <byorgey@seas.upenn.edu> wrote:
Well, it sounds nice, but it's pretty inefficient.  And by "pretty
inefficient" I mean "horrendously, terribly inefficient" -- there are
n! permutations of a list of length n, so this would take time O(n!)
as opposed to O(n); O(n!) is even worse than O(2^n).

-Brent
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners