[Haskell-beginners] permuting a list
Brent Yorgey
byorgey at seas.upenn.edu
Thu Feb 12 13:33:29 EST 2009
On Thu, Feb 12, 2009 at 11:58:21AM -0500, Andrew Wagner wrote:
> >
> > <rant>
> > It seems everyone has just been reading the first few words of Jan's
> > email and not the actual content. Jan is clearly trying to write a
> > *random list shuffling* function, not a function to generate
> > permutations. Let's try to be helpful, people...
> > </rant>
> >
>
> Agreed, I've been quite confused by this thread. In the spirit of laziness,
> though, wouldn't it seem like the "right" method is to generate all the
> permutations lazily, and then choose a random element of that list?
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
More information about the Beginners
mailing list