On Sat, Jun 26, 2010 at 3:51 PM, sharad kumar <sharad20073...@gmail.com>wrote:
> 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.
>
> I'm assuming that the random function can generate uniformly distributed
random numbers between 0 and n(excluding n), where n is an +ive integer.
following relies on the fact that probability of choosing the nth character
is 1/n and choosing any of the previous characters is (n-1)/n.
def get_random_obj( objstream ):
count = 1
obj = objstream.get()
while not objstream.end():
r = rand(0, count)
if r == 0:
obj = objstream.get()
else:
objstream.get() #discard
return obj
Anil
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
