[Haskell-beginners] permuting a list

[Thomas Davie]

On 12 Feb 2009, at 19:33, Brent Yorgey wrote:

> 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).

Would it?  We're talking about lazyness here... it's not gonna compute  
one it doesn't need, and if you're somewhat cleverer with your permute  
function than I was, I'm sure you can do as little computation as the  
imperative version.

Bob