Algoriothm/puzzle

Assume your computer is reading characters one by one from a stream (you don't know the length of the stream before ending). Note that you have only one character of storage space (so you cann't save the characters you've read to a something like a strong). When you've finished reading you should return a character out of the stream with equal probability.
shwetasingh206Asked:
Who is Participating?
 
ozoConnect With a Mentor Commented:
perldoc -q "How do I select a random line from a file"
       How do I select a random line from a file?

       Here's an algorithm from the Camel Book:

               rand($.) < 1 && ($line = $_) while <>;

       This has a significant advantage in space over reading the whole file
       in.  You can find a proof of this method in The Art of Computer
       Programming, Volume 2, Section 3.4.2, by Donald E. Knuth.
0
 
Infinity08Connect With a Mentor Commented:
>> a character out of the stream with equal probability.

with equal probability ? What do you mean ? You want a uniformly random character from the stream without knowing the size of the stream ?

If so, simply do something like this :

1st character : save it in the buffer
2nd character : save it in the buffer with 1/2 probability
3rd character : save it in the buffer with 1/3 probability
...
nth character : save it in the buffer with 1/n probability
...
0
 
ozoCommented:
So for single characters
stream | perl -ne 'BEGIN{$/=\1}$char = $_ if rand($.) < 1;END{print $char}'
0
 
NovaDenizenConnect With a Mentor Commented:
This is the way to do it, but it requires additional storage to hold the count of the number of characters you've read.  There is a counter behind $., or perl is using ftell() and the counter is hidden in the runtime libraries.

So really you need something like ceil(lg(n)) + 8 bits of storage to handle up to n characters of input.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.