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.
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. | ||
| ||
StarCraft 2 StarCraft: Brood War Britney 19974 Dota 2GuemChi 3835 Rain 3052 BeSt 539 Shuttle 285 Hyuk 258 Leta 199 Shinee 169 hero 150 Free 56 [ Show more ] League of Legends Counter-Strike Other Games summit1g9310 ceh9481 Livibee290 DeMusliM172 NuckleDu127 Mew2King76 Trikslyr56 Pyrionflax41 Liquid`Ken13 Organizations Dota 2 Other Games StarCraft: Brood War StarCraft 2 StarCraft: Brood War
StarCraft 2 • Berry_CruncH168 StarCraft: Brood War• aXEnki • intothetv • Gussbus • Kozan • IndyKCrew • LaughNgamez Trovo • Laughngamez YouTube • Migwel • Poblha League of Legends |
Replay Cast
OSC
Replay Cast
GSL Code S
Solar vs DongRaeGu
NightMare vs ByuN
OSC
StarsWar
Maru vs Spirit
ShoWTimE vs GuMiho
Firefly vs herO
Oliveira vs SKillous
Chat StarLeague
H.4.0.S
Chat StarLeague
StarsWar
[ Show More ] Chat StarLeague
BSL
Dewalt vs Zhanhun
ForJumy Cup
Chat StarLeague
|
|