Okay..missed it..thnx fr info..
Your approach is nice..it took me some time to understand your code's
though.. Great answer!!
On Aug 26, 2012 3:55 AM, "Dave" <dave_and_da...@juno.com> wrote:
> @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> 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/*
>>>>> *ms**g/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<https://groups.google.com/d/msg/algogeeks/-/crET-x06vpkJ>
>>> .
>>> 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/-/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.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
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.
