Solved

Algoriothm/puzzle

Posted on 2008-10-03
5
428 Views
Last Modified: 2010-10-05
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.
0
Comment
Question by:shwetasingh206
  • 2
5 Comments
 
LVL 84

Accepted Solution

by:
ozo earned 168 total points
ID: 22632035
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
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 166 total points
ID: 22632041
>> 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
 
LVL 84

Expert Comment

by:ozo
ID: 22632078
So for single characters
stream | perl -ne 'BEGIN{$/=\1}$char = $_ if rand($.) < 1;END{print $char}'
0
 
LVL 22

Assisted Solution

by:NovaDenizen
NovaDenizen earned 166 total points
ID: 22636477
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

Featured Post

Are your AD admin tools letting you down?

Managing Active Directory can get complicated.  Often, the native tools for managing AD are just not up to the task.  The largest Active Directory installations in the world have relied on one tool to manage their day-to-day administration tasks: Hyena. Start your trial today.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
The Sorcerer's Cave game Java 11 1,025
Calculating an algorithm from a set of pre generated numbers 5 183
SQL Query 9 170
Math between Excel and approximations 15 104
Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
This video shows how to quickly and easily add an email signature for all users on Exchange 2016. The resulting signature is applied on a server level by Exchange Online. The email signature template has been downloaded from: www.mail-signatures…
Established in 1997, Technology Architects has become one of the most reputable technology solutions companies in the country. TA have been providing businesses with cost effective state-of-the-art solutions and unparalleled service that is designed…

778 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question