[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