Math/Computer Science Problem

Slithe

United States985 Posts

January 22 2008 23:17 GMT

You have a list of unknown size N, that you are only allowed to traverse once. The goal is to devise a method to create a set of size K that is random and uniformly distributed among all the possible subsets of N that are size K. What is the method?

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

January 22 2008 23:39 GMT

I'm too tired to think it through but will the 'picks' be evenly distributed if you choose the first K elements and then (if N > K) eliminate a random (evenly distributed) element of the K+1 (the old picks and the next one on the list)?
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

January 23 2008 00:31 GMT

Yeah, that's how you must do it. Up to K you obvioulsy have to pick all elements to your set. When you run through the n:th element (n>K), you use it to replace a random element in your previous set of K elements with a probability K/n. Leave the set unchanged with prob (n-K)/n. Use induction to prove that it works.

zdd

1463 Posts

January 23 2008 00:31 GMT

I think it would be something like this:
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

January 23 2008 01:30 GMT

zdd, your second algorithm isn't O(1) or O(K) memory, it's O(n) memory, which breaks the problem constraints.

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

January 23 2008 01:35 GMT

Yeah, I think that Cascade's idea will work. Your memory space is O(K), not O(N), so it's fine.

Slithe

United States985 Posts

January 23 2008 02:41 GMT

Yes Cascade has the right answer. Good job! I'll be posting up a significantly more difficult problem now, which I actually don't quite know the answer to, but I have a basic idea.

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.

Please or register to reply.