[Haskell-beginners] Re: permuting a list

[Heinrich Apfelmus]

Daniel Fischer wrote:
> Thomas Davie wrote:
>> Brent Yorgey wrote:
>>> Andrew Wagner wrote:
>>>> Brent Yorgey 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.
> 
> But to find the k-th permutation, it would have to traverse k cons
> cells containing thunks, wouldn't it?
> 
> Well, the following is O(n^2), not quite O(n), but at least it's not
>  "horrendously, terribly inefficient".

That of course begs the question whether there is a faster but purely
functional algorithm for generating random permutations without indexes
and arrays?

The answer is a resounding "yes" and the main idea is that shuffling a
list is *essentially the same* as sorting a list; the minor difference
being that the former chooses a permutation at random while the latter
chooses a very particular permutation, namely the one that sorts the input.

For the full exposition, see

   http://apfelmus.nfshost.com/random-permutations.html


Regards,
apfelmus

-- 
http://apfelmus.nfshost.com