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