<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?