[Haskell-beginners] permuting a list

[Brent Yorgey]

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