[Haskell-beginners] permuting a list
Andrew Wagner
wagner.andrew at gmail.com
Thu Feb 12 13:45:22 EST 2009
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 at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20090212/8dc5f5ec/attachment-0001.htm
More information about the Beginners
mailing list