@Don: Note that a[j] - j is the number of non-excluded responses < a[j].
Here is the algorithm I would use:
k = rnd(N - S);
if( k < a[0] )
j = -1;
else
{
Use a binary search to find the largest j with 0 <= j < S such that
a[j] - j <= k;
}
return k + j + 1;
The algorithm uses O(1) extra space and O(log S) time.
Dave
On Tuesday, October 8, 2013 9:48:58 AM UTC-5, Don wrote:
> Provide a function which returns a value randomly and uniformly selected
> from the range 0..N-1 excluding values in the array a[S] containing sorted
> values in the same range. A rejection algorithm would work well enough if S
> is much smaller than N, but what if N is large and S is slightly smaller?
>
> Assume that you are given a pseudo-random generator int rnd(int n) which
> returns a pseudo-random number uniformly distributed in the range 0..n-1.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
