oops! yeah you also need to increment the count inside...
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
count += 1
return obj
Anil
On Sat, Jun 26, 2010 at 11:45 PM, Dave <dave_and_da...@juno.com> wrote:
> Since count is always 1, doesn't rand(0, count) always return 0? So
> you always get the last item in the input.
>
> Dave
>
> On Jun 26, 11:00 am, Anil C R <cr.a...@gmail.com> wrote:
> > 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<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
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.
