On Thu, Feb 12, 2009 at 08:19:46PM +0100, Thomas Davie wrote:
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.
Indexing into a list is still O(n) in the index, whether you actually compute the elements or not. That is, if you're actually building a list of permutations, then even if you don't compute anything about the permutations you don't need, just traversing through the spine of the list to get the one you want will take a very long time---O(n!)---for reasonably large n. However, you can actually write a pure function with type Int -> [a] -> [a] which just computes which permutation "would be" at the given index, without ever actually constructing a list of them. I'll leave this as an interesting exercise (hint: convert the input number to "base factorial"...), although I still think it's not going to be quite as fast as the imperative version (at least O(n lg n)). -Brent