[Haskell-beginners] permuting a list

[Brent Yorgey]

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