JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Algorithm Discussions General Algorithm Discussions Choose random array element satisfying certain property
 Choose random array element satisfying certain property | Reply Suppose I have a list, called elements, each of which does or does not satisfy some boolean property p. I want to choose one of the elements that satisfies p by random with equal distribution. I do not know ahead of time how many items satisfy this property p.Will the following code do this?:```pickRandElement(elements, p) randElement = null count = 0 foreach element in elements if (p(element)) count = count + 1 if (randFloat(0.0, 1.0) < 1.0 / count) randElement = element   return randElement ```(randFloat(f1, f2) returns a random float f with f1 <= f < f2.)
 Re: Choose random array element satisfying certain property (response to post by reiners) | Reply No. It will have a 100% probably of picking the first element if the first element satisfies p.To correct, you will need to count all elements first, and then call randFloat() once. (Or maybe you've just indented incorrectly?)If you expect there to always be a sufficient percentage which satisfy p(), you can also use rejection sampling - just pick elements at random and reject picks where !p(element).EDIT: I somehow thought there was a return after the assignment.
 Re: Choose random array element satisfying certain property (response to post by eraserhd) | Reply I've indented correctly. That's true that it will set randElement to the first element that satisfies p, but the method doesn't return at that point. It continues iterating, possibly changing the value of randElement again. For example, when it reaches the second element satisfying p, it will replace the first element with a probability of 1/2.
 Re: Choose random array element satisfying certain property (response to post by reiners) | Reply It should work. Proof:the elements that don't satisfy p are irrelevant, since they are simply skipped. So we have a list of n elements (1..n). The probability that element i is the output, is equal to the probability that it will be chosen and not replaced later on:`P(X = i) = 1/i * i/(i + 1) * (i + 1)/(i + 2) * ... * (n - 1)/(n) = 1 / (i/i) / ((i+1)/(i+1)) / ... / n = 1/n`
 Re: Choose random array element satisfying certain property (response to post by decowboy) | Reply A bit more intuitive way to see it: after each iteration each element satisfying p up to that point is equally likely, by induction.
 Re: Choose random array element satisfying certain property (response to post by decowboy) | Reply Funny. I was asked that question (worded differently) in an interview at Google Belo Horizonte. I gave this same algorithm, but instead of if (randFloat(0.0, 1.0) < 1.0 / count) I used if (randInt(0, count) == 0), where randInt(0, n) returns a random integer (uniformly) in the range [0..n). As far as I can tell, it's exactly the same algorithm (even slightly better as there are no floating point operations), but the interviewer kept saying that it was not the right answer. First I showed him an empirical proof (using an example with a few items) and then I showed an inductive proof, but he just said I was wrong and it was time to move for the next question. Weird. Anyone can tell me what's wrong with it?edit - in the question I was given there was no boolean property that had to be satisfied, just a collection of items (of course, the size of the collection was unknown and the algorithm had to be O(n) in time and O(k) in space AND we could only iterate once through the collection).
 Re: Choose random array element satisfying certain property (response to post by gsais) | Reply Probably he wanted to see how did you defend, and were you sure with your solution. :P