ricardobeat wrote:
If you need performance, this should be it:
http://jsbin.com/uvuzi/edit
It sorts the rows using the "Fisher-Yates" shuffling algorithm.
Despite throwing elements around in an array, it's faster than the
pure mathematical solution because you don't need to filter out
duplicate random numbers. An even greater improvement can be made by
using the style.display property directly.
First of all, thanks for your code. I learned something new today. I
never realized that I could reassign the elements of a jQuery collection
in that manner.
I don't know why I brought up performance for a client-side JavaScript
issue! It's probably not at all relevant to the OP's problem. But I
think both your technique and mine should have similar performance. The
key factor in either of ours is the number of calls to Math.random(),
and both of us call that $rows.length times.
Sean O's technique has a worst-case time that is infinite, but it, or a
slight modification of it [1], has an expected time much shorter than
either of ours. In the ten-out-of-fifty case we were working with, our
techniques require 50 iterations, where in his the expected number of
iterations is 11.033. In your ten-out-of-one-thousand example, ours
would be 1000, and his expected number is below 10.05. With the
modification [1], the worst case would be if the number to be selected
were half of the total rows, and then the number of iterations seems to
be about ln(2) * $rows.length, although I haven't attempted to prove this.
This is related to the Coupon Collector's Problem [2]. I'm pretty sure
the exact expected number of iterations of Sean's technique is
sum_{i=1}^{SELECTED} {TOTAL / (TOTAL - i + 1)}
But hey, let's get back to jQuery! :-)
-- Scott
[1] The modification would be, when the requested number of rows is
greater than half the total number of rows, to switch to running the
same algorithm to choose the number of *unselected* rows.
[2] http://www.google.com/search?q=coupon+collector+problem
