Dave's response is the right idea. A binary search can find the number of
"holes" in the set of valid results.
Here is my solution:
int getRndVal(int N, int S, int *a)
{
// We are going to return the xth valid value
int x = rnd(N-S);
// Binary search to find the number of values in a
// which are less than the xth valid value
int mid, min = 0, max = S;
while(min < max)
{
mid = (min + max) / 2;
if (a[mid] > (x+mid)) max = mid;
else min = mid+1;
}
// Min is now the number of values in a[S] less than the xth
// valid result, so the xth value is x+min.
return x+min;
}
You can prove that it works by trying all possible values of x and
verifying that it produces the set of valid responses.
Don
On Thursday, October 10, 2013 12:41:10 AM UTC-4, Dave wrote:
>
> @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.
