shuffling lines in a stream

[Andrei Alexandrescu]

The high traffic enjoyed by "random k-sample of a file" confirms that 
plenty of people around here have idle cycles ready to be spent on fun 
tasks.

In that vein, here's another problem. Say you want to randomly shuffle 
lines in a stream. You don't know the size beforehand, and one pass is 
preferable. The stream can be larger than the working memory, but not an 
unbounded amount of times larger. Also lines in the stream can be 
unbounded, but it is guaranteed that at least a nonzero fraction of the 
file fits in working memory.

You can use temporary files, but of course minimizing their total size 
is recommended. Speed is of course important. Draft your solution and 
explain why you think it's correct and advantageous.

In case you hate random stuff, just wait; the next problem won't have 
any random element in it :o).


Andrei