On Wed, 26 Apr 2006, Rob wrote:
n is on order of 2^15 or bigger. m can be any value between 1 and n, I
need to be able to handle all cases efficciently.
Depends on the relative sizes of n and m. If m is comperable in size to
n, then you can just do a random shuffle ( takes O(n)), then pick off the
first m numbers.
Random shuffle in O(n)? How?
If m is small compared to n, just have an efficient
set implementation (with hashes), pick random elements, and make sure
they don't match. Here you can trade off memory vs time. Pick an array
of size k bits (bigger k == more mem, less time), to insert a number i,
take a random hash of i that maps to j where j is in [0,k-1], and set
the jth bit to one. Testing is just that proceedure. If k is small,
you will need to implement a hash bucket to catch collisions, but that
is easy enough as well.
I'm not sure the results would be truly random; that would at the very
least depend on the hash used. Plus, I'd rather avoid non-deterministic
algorithms (i.e. picking a random number, realising it's been picked and
trying again until you get one that hasn't been).
Alexey
