@Kunal: Yes. You are missing that you don't know the number of words in the
file in advance. So, to use your method, you would have to read the file
once to find n, and then read through it again to select the lucky_pos th
word. The method I proposed only requires reading the file once.
Furthermore, assuming that rand() produces a random non-negative integer,
rand()%n is not equiprobable for all values of n. Consider n = 3. Then
since rand() takes on 2^31 values, rand()%3 cannot take on the values 0, 1,
and 2 with equal probability since 2^31 is not divisible by 3.
Dave
On Saturday, August 25, 2012 1:44:03 PM UTC-5, Kunal Patil wrote:
> How about using rand()%n ??
> Like, calculate lucky_pos = rand()%n
> Then print word at lucky_pos th position...
> Am I missing anything? All words are still equiprobable to get printed
> right?
> On Aug 20, 2012 11:45 AM, "Dave" <dave_an...@juno.com <javascript:>>
> wrote:
>
>> @Navin: Okay. Here is a paraphrase. Assume double function random()
>> returns a uniformly distributed random number >= 0.0 and < 1.0.
>>
>> read first word from file into string save;
>> int i = 1
>> while not EOF
>> {
>> read next word from file into string temp;
>> i++;
>> if( i * random() < 1.0 )
>> copy temp to save;
>> }
>> print save;
>>
>> Dave
>>
>> On Monday, August 20, 2012 12:02:54 AM UTC-5, Navin Kumar wrote:
>>
>>> @Dave sir, I didn't get your logic. Can you please elaborate it?
>>>
>>> On Sun, Aug 19, 2012 at 4:08 AM, Dave <dave_an...@juno.com> wrote:
>>>
>>>> @Navin: Here is the algorithm:
>>>>
>>>> Save the first word.
>>>> For i = 2, 3, ..., n = number of words in the file
>>>> replace the saved word with the i-th word with probability 1/i.
>>>> When EOF is reached, every word in the file will have probability 1/n
>>>> of being the saved word. Print it.
>>>>
>>>> Dave
>>>>
>>>> On Saturday, August 18, 2012 1:28:56 AM UTC-5, Navin Kumar wrote:
>>>>
>>>>> Print a *Random word* from a file. Input is "path to a file",
>>>>>
>>>>> constraints- No extra memory like hashing etc. All the words in the
>>>>> file should have equal probability.
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To view this discussion on the web visit https://groups.google.com/d/**
>>>> msg/algogeeks/-/HxO-wNzEP9gJ<https://groups.google.com/d/msg/algogeeks/-/HxO-wNzEP9gJ>
>>>> .
>>>>
>>>> To post to this group, send email to algo...@googlegroups.com.
>>>> To unsubscribe from this group, send email to algogeeks+...@**
>>>> googlegroups.com.
>>>> For more options, visit this group at http://groups.google.com/**
>>>> group/algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en>.
>>>>
>>>
>>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/crET-x06vpkJ.
>> To post to this group, send email to algo...@googlegroups.com<javascript:>
>> .
>> To unsubscribe from this group, send email to
>> algogeeks+...@googlegroups.com <javascript:>.
>> 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 view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/pvqb27sRhFAJ.
To post to this group, send email to algogeeks@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.
