On Thu, Apr 27, 2006 at 12:20:48AM +0000, Alexey Toptygin wrote: > I've got a question about the most efficient known way to solve a > particular problem (randomly pick m distinct integers in the range > [0,n-1]) Can someone familiar with the CS department point me to a good > professor to ask about this? Thanks.
You could just ask me :-) 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. 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. - Rob .
