Difference between revisions of "TADM2E 2.43"
(Alternative solution to TADME2E 2.43) |
(Since the problem invited an initial solution with a known set size, added a description of such a solution.) |
||
| Line 1: | Line 1: | ||
| + | A solution for the known <math>S</math> size: While <math>S'</math> size is less than <math>k</math>, look at the first element of <math>S</math>. For each iteration, calculate the probability of admitting the element from <math>S</math> into <math>S'</math> as <math>\frac{k - \text{size}(S')}{\text{size}(S)}</math>, and admit elements accordingly. Each step, remove the first element from <math>S</math>, and update the probability ratio accordingly. | ||
| + | |||
Whether we know <math>n</math> or not we can sample <math>k</math> values uniformly by assigning a random value to each element, sorting, and taking the top <math>k</math> values. However, this is not very efficient so instead we can use a <i>priority queue</i> of size <math>k</math> with random priority. | Whether we know <math>n</math> or not we can sample <math>k</math> values uniformly by assigning a random value to each element, sorting, and taking the top <math>k</math> values. However, this is not very efficient so instead we can use a <i>priority queue</i> of size <math>k</math> with random priority. | ||
Revision as of 02:11, 2 January 2019
A solution for the known $ S $ size: While $ S' $ size is less than $ k $, look at the first element of $ S $. For each iteration, calculate the probability of admitting the element from $ S $ into $ S' $ as $ \frac{k - \text{size}(S')}{\text{size}(S)} $, and admit elements accordingly. Each step, remove the first element from $ S $, and update the probability ratio accordingly.
Whether we know $ n $ or not we can sample $ k $ values uniformly by assigning a random value to each element, sorting, and taking the top $ k $ values. However, this is not very efficient so instead we can use a priority queue of size $ k $ with random priority.
Alternatively, we can iterate over the elements in $ S $ from $ i = 0 $ until $ S[i] $ is empty. If $ i < k $, $ S'[i] = S[i] $. After that, for each $ i $, replace a random element in $ S' $ with $ S[i] $, with probability $ \frac{k}{i + 1} $ of performing the replacement rather than skipping to the next.
Return to Algo-analysis-TADM2E ...
