Oops. The statement int I = 1 in the above should be int k = 1. Sorry.
Dave
On Sunday, May 5, 2013 9:10:37 PM UTC-5, Dave wrote:
> @Nishant: I'm assuming that you don't know the number of words in the
> file, and that you don't want to store them all. Here is an algorithm that
> requires you to store only two words and an integer.
> Assume double function random() returns a uniformly distributed random
> number >= 0.0 and < 1.0.
>
> int i = 1
> read first word from file into string save;
> while not EOF
> {
> read next word from file into string temp;
> k++;
> if( k * random() < 1.0 )
> copy temp to save; // happens with probability 1/k
> }
> print save;
> Here is why this works. The k-th word is initially selected with
> probability 1/k. It is replaced with the k+1st word with probability
> 1/(k+1). Thus, the k-th word is not replaced with the k+1st word with
> probability 1 - 1/(k+1) = k/(k+1). Similarly, it is not replaced with the
> k+2nd word with probability (k+1)/(k+2). Etc. This means that the k-th word
> was selected and survives to the EOF with probability
>
> 1/k * k/(k+1) * (k+1)/(k+2) * ... * (n-1)/n, where n is the number of
> words in the file.
>
> Every numerator equals the preceding denominator, so the product collapses
> to 1/n. This is true for any k with 1 <= k <= n, proving that the algorithm
> produces the desired result.
>
> Dave
>
> On Sunday, May 5, 2013 7:44:01 AM UTC-5, Nishant Pandey wrote:
>
>> Hi Guys,
>>
>> In this problem i am wondering how it will be done without extra memory
>> space, though we can easily do it with hashing and random funcs().
>> Is there any solution for this , Please help.
>>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
