@all-This is almost the same question asked in facebook..
Dave sir is correct!
Example-file contain only a b a c;
Then step1:
save a;
step2:
save b with probability of value 0 by rand()%2;
therefore pr[1]=1/2;pr[2]=1/2;
step3;
save a with probability of value 0 by rand()%3;
therefore
@Kailash: I assumed a function random() which generates uniformly
distributed double precision random numbers between 0 and 1. Usually such a
generator would produce numbers with 53 bit precision, so I guess that is
between 15 and 16 digits after the decimal point. Just google random
number
@Pankaj: My only complaint is that rand()%n is not uniformly distributed
between 0 and n-1. To see this, suppose rand() produces positive 32-bit
integers, so they have the range 0 to 2^31 - 1 = 2,147,483,647. Now,
suppose there are 100,000 words in the file. When you are computing
@Dave Sir-Got ur point..thnks!!
--
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
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
@Dave: Can you throw some light on random() function?? How it is generating
numbers between 0.0 and 1.0, and how many digits are there after the
point...because if there is only one digit then we will not be able to
print words after 10th place because 10*0.1(lowest number generated by
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_and_da...@juno.com wrote:
@Navin: Okay. Here is a paraphrase. Assume
@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.
@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 )
@Dave sir, I didn't get your logic. Can you please elaborate it?
On Sun, Aug 19, 2012 at 4:08 AM, Dave dave_and_da...@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
@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
11 matches
Mail list logo
