l*********t
发帖数: 89 | 1 Q:
Given a linked list of N floating point numbers, write an algorithm to
populate an M long array with numbers from the linked list where M < N.
Every number in the linked list must have equal chance of appearing in the
array, but a number may not appear twice (note that there are no repeats in
the linked list).
Write an algorithm where N is known at the start, then an algorithm where N
is not initially known. The list may only be traversed once.
A:
Assuming you have access to a good RNG, and that the linked list does not
contain cycles:
For the first M elements of the linked list, include every single element
Then, starting at i=M+1 and above, include the ith element with probability
p=M/i. If it's included, put it at each of the positions of the array with
equal probability 1/M
The probability of any element of the linked list being included in the
array is M/N.
没咋看懂答案啥意思，望大虾指点。 | j********t
发帖数: 97 | 2 While scanning i-th entry of list, we need to decide whether polulate i-th
entry or not and what position i-th entry should be put.
Firstly, accept i-th entry by prob M/i. Then choose position in
array randomly, i.e. prob 1/M. Thus, the i-th entry is populated by (M/i) * (
1/M) = 1/i.
suppose i-1 th entry is populated by 1/(i-1) before. Then after populating i
-th entry, i-1 th prob become 1/(i-1) * (1 - 1/i) = 1/i | x**********2
发帖数: 3 | 3 Prove with induction:
1. N=M+1, each element is selected with M/(M+1)
2. for the first N elements, assume each element is selected with M/N
3. When it comes to the (N+1)th elements: Evidently, the (N+1)th element is
chosen with M/(N+1). Now calculate the probability for the first N elements.
M/(N+1)*M/N*(M-1)/M + (N+1-M)/M * M/N = M/(N+1). So, all elements are
chosen with probability of M/(N+1) | l*********t
发帖数: 89 | 4 Thank u, junorquant. But the probability should be a constant, so 1/i seems
not to be on the right track..
* (
i
【在 j********t 的大作中提到】
: While scanning i-th entry of list, we need to decide whether polulate i-th
: entry or not and what position i-th entry should be put.
: Firstly, accept i-th entry by prob M/i. Then choose position in
: array randomly, i.e. prob 1/M. Thus, the i-th entry is populated by (M/i) * (
: 1/M) = 1/i.
: suppose i-1 th entry is populated by 1/(i-1) before. Then after populating i
: -th entry, i-1 th prob become 1/(i-1) * (1 - 1/i) = 1/i
| l*********t
发帖数: 89 | 5 It works. Thank u, XiaZheTeng12~
is
elements.
【在 x**********2 的大作中提到】
: Prove with induction:
: 1. N=M+1, each element is selected with M/(M+1)
: 2. for the first N elements, assume each element is selected with M/N
: 3. When it comes to the (N+1)th elements: Evidently, the (N+1)th element is
: chosen with M/(N+1). Now calculate the probability for the first N elements.
: M/(N+1)*M/N*(M-1)/M + (N+1-M)/M * M/N = M/(N+1). So, all elements are
: chosen with probability of M/(N+1)
|
|
