EPTRemember:
1) You do not know N. Your answer should not rely on N, i.e. your memory size should not be based on N in any way.
2) You can only traverse the list once.
3) K is less than or equal to N, so there is always at least one possible set.
Math/Computer Science Problem
| Blogs > Slithe |
|
Slithe
United States985 Posts
Remember: 1) You do not know N. Your answer should not rely on N, i.e. your memory size should not be based on N in any way. 2) You can only traverse the list once. 3) K is less than or equal to N, so there is always at least one possible set. | ||
Asta
Germany3491 Posts
I think not... :D Because the first ones will be much likelier to be discarded than the last ones. Which brings us back to the initial problem that you don't know to what degree you have to favor the first ones because it depends on N. Hum... | ||
|
Cascade
Australia5405 Posts
| ||
|
zdd
1463 Posts
let's say n is an array of ascending integers, k is an int, set_k is an empty array the set n would be distributed something like this: [1 - k][k+1 - 2k][2k+1 - 3k]... i=0; for each $element in n { if(i<k){ if(random(1,k)=k){ $set_k[i]=$element; i++; } } } I dunno, statistically each element in n would have a 1/k chance to become an element in set_k, so I guess in every k elements in set n there should only be around 1 element that goes into set k. edit: oh nvm, maybe you could just copy set "n" to set "set_k", then remove random elements from set_k until length(set_k) is equal to K int K = <some value>; int i=0; int[] set_k; for each $element in n { set_k[i]=$element; i++; } while(length(set_k) != K) { delete(set_k[random(0, length(set_k))]); } output set_k edit2: cascade's idea is different, because he uses k+1 memory instead of n it would be implemented something like: int K = <some value>; int i=0; int[] set_k; function randomkn(k, n){ //run random(1,n) k times $var=false; while (k>0){ k--; if (random(1, n) == n){$var=true;} } return $var; } for each $element in n { if (i<K+1){ set_k[i]=$element; i++; } else if (randomkn(K, length(n))) { set_k[random(0,K+1)]=$element; } } output set_k | ||
|
BottleAbuser
Korea (South)1888 Posts
I'm not sure if I follow your first one. I think the actual solution has something to do with finding the probability that the nth element should be included in the set, given k. Obviously (at least to me, I could be wrong), the first element should be selected with (N/K) probability. Then, k := K - 1 if the first element was selected, and n := N - 1 , and repeat for the rest of the elements. This is guaranteed to return K elements. There might seem to be a problem with the later elements (especially the last element) having a higher than (N/K) probability to be selected, but I think this is not the case. For the last L elements to always be selected, (n/k == 1) must hold. However, the probability of this happening is quite small if N is large (unless K is equally large). I'm too lazy to calculate it myself (OK, I'm too stupid to do it), but I think if you go through with it, you'll find that the probability that the last L elements are arrived at with (k==n) is the same as 1 minus the probability that they are arrived at with (k==0). Oh, shit, you don't know N. My idea is bunk. | ||
|
BottleAbuser
Korea (South)1888 Posts
| ||
|
Slithe
United States985 Posts
Regarding this problem: Basically, since you don't know how many elements are in the list, you have to make sure at each iteration through the list, all elements up to that iteration have an equal probability, k/i, of being in the set, where "i" is the current index. If you work around that idea, then the answer comes more easily, or at least for me it did. For Asta's answer: The key there was that you don't always discard. It seems that you already realized the problem, so you probably would have realized the fix eventually. For zdd's answers: The first one is incorrect because, all elements will have probably 1/k of being in the set until the set is full, and then the next elements have probability 0. In the first place, 1/k is incorrect, and the correct probability to aim for is k/i. The second one, BottleAbuser pointed out the problem, which is that you require O(n) memory, which is not allowed. | ||
| ||
