I offer below a programming exercise, more in the spirit of fun than
being really challenging. The effort needed isn't trivial but it
shouldn't be huge either. The exercise was inspired by some recent
discussion in comp.lang.{c,c++}.

Exercise: write code to give a definition for the interface below
(the interface is written for C, but feel free to write a solution,
along with the corresponding interface, in a different language):

typedef unsigned long UL;
typedef UL RNG( void );

UL choose_k_of_n_then_select(
RNG rng, UL rng_max, UL n, UL k, UL j
);

The parameters may be assumed to obey the following constraints
(i.e., the constraints may be asserted at the start of the function
definition)

rng != 0
j <= k
k <= n
n < rng_max

Problem: rng is a random number generator function that returns
values uniformly distributed between 0 and rng_max, inclusive (so
rng_max+1 possible values. Choose k+1 distinct random values (using
the supplied function rng) in the range between 0 and n, inclusive
(so n+1 possible values). Of these k+1 distinct values, return the
j'th value in ascending order (so for j=0 return the least value,
for j=k return the largest value, etc).

It's important that the random selection be unbiased, with all of
the (n+1) choose (k+1) possible sets being equally likely (of
course under the assumption that rng is a "good" random number
generator). However it is also important that the code work
even if rng is "poor", as for example it first returns all the
even numbers and then returns all the odd numbers. It is safe
to assume that rng is not pathologically bad: it might be
really awful, but it will not be malicious.

For purposes of testing, if k is set equal to n, the result of
any j <= k should be equal to j, so

choose_k_of_n_then_select( rng, -1, 100, 100, 0 ) == 0
choose_k_of_n_then_select( rng, -1, 100, 100, 1 ) == 1
...
choose_k_of_n_then_select( rng, -1, 100, 100, 99 ) == 99
choose_k_of_n_then_select( rng, -1, 100, 100, 100 ) == 100

(with 'rng' being any suitable rng, even a poor one).

Note that rng_max might be close to n, which means it's important to
take that possibility into account in producing random numbers, so
that there is no bias.

Good solutions should not impose any artificial limitations on the
values of j, k, n, and rng_max.

I have written code to do this but will not be posting it for at
least a week. Have fun!

On Monday, January 30, 2023 at 4:00:45 AM UTC, Tim Rentsch wrote:
> I offer below a programming exercise, more in the spirit of fun than
> being really challenging. The effort needed isn't trivial but it
> shouldn't be huge either. The exercise was inspired by some recent
> discussion in comp.lang.{c,c++}.
>
> Exercise: write code to give a definition for the interface below
> (the interface is written for C, but feel free to write a solution,
> along with the corresponding interface, in a different language):
>
> typedef unsigned long UL;
> typedef UL RNG( void );
>
> UL choose_k_of_n_then_select(
> RNG rng, UL rng_max, UL n, UL k, UL j
> );
>
> The parameters may be assumed to obey the following constraints
> (i.e., the constraints may be asserted at the start of the function
> definition)
>
> rng != 0
> j <= k
> k <= n
> n < rng_max
>
> Problem: rng is a random number generator function that returns
> values uniformly distributed between 0 and rng_max, inclusive (so
> rng_max+1 possible values. Choose k+1 distinct random values (using
> the supplied function rng) in the range between 0 and n, inclusive
> (so n+1 possible values). Of these k+1 distinct values, return the
> j'th value in ascending order (so for j=0 return the least value,
> for j=k return the largest value, etc).
>
> It's important that the random selection be unbiased, with all of
> the (n+1) choose (k+1) possible sets being equally likely (of
> course under the assumption that rng is a "good" random number
> generator). However it is also important that the code work
> even if rng is "poor", as for example it first returns all the
> even numbers and then returns all the odd numbers. It is safe
> to assume that rng is not pathologically bad: it might be
> really awful, but it will not be malicious.
>
> For purposes of testing, if k is set equal to n, the result of
> any j <= k should be equal to j, so
>
> choose_k_of_n_then_select( rng, -1, 100, 100, 0 ) == 0
> choose_k_of_n_then_select( rng, -1, 100, 100, 1 ) == 1
> ...
> choose_k_of_n_then_select( rng, -1, 100, 100, 99 ) == 99
> choose_k_of_n_then_select( rng, -1, 100, 100, 100 ) == 100
>
> (with 'rng' being any suitable rng, even a poor one).
>
> Note that rng_max might be close to n, which means it's important to
> take that possibility into account in producing random numbers, so
> that there is no bias.
>
> Good solutions should not impose any artificial limitations on the
> values of j, k, n, and rng_max.
>
> I have written code to do this but will not be posting it for at
> least a week. Have fun!

Just to check, we're free to "use" rng any way we want to, as long as the results are unbiased? For example, a naïve approach might be to try again if we get a value bigger than n, but if rng_max is between 2n+2 and 3n then we could have 0 or n+1 mean 0, 1 or n+2 mean 1, etc, and only have to reject values bigger than 2n+2. Also, do we have to select numbers in the range 0 to n and reject any duplicates, or can we rig things so we are selecting randomly only from those numbers not yet selected?

Paul N <gw7rib@aol.com> writes:

> On Monday, January 30, 2023 at 4:00:45 AM UTC, Tim Rentsch wrote:
>
>> [choosing some distinct values using 'rng' for random numbers]
>
> Just to check, we're free to "use" rng any way we want to, as long as
> the results are unbiased? For example, a naive approach might
> be to try again if we get a value bigger than n, but if rng_max is
> between 2n+2 and 3n then we could have 0 or n+1 mean 0, 1 or n+2 mean
> 1, etc, and only have to reject values bigger than 2n+2.

Right. In general if we want to get an unbiased uniform value in
some range, some results from rng() will have to be passed over
in cases where the number of possible values from calling rng()
is not an exact multiple of the number of values in the range
(which is n+1 in your example). It's necessary to do something
along these general lines, as otherwise the results will be
biased in one direction or another.

> Also, do we
> have to select numbers in the range 0 to n and reject any duplicates,
> or can we rig things so we are selecting randomly only from those
> numbers not yet selected?

Either approach is valid as far as getting the right answer is
concerned. You might prefer one of these methods over the other,
or perhaps yet a different method, considering some other aspect
of the problem, such as run-time performance or how much memory
is needed.

On Monday, 30 January 2023 at 05:00:45 UTC+1, Tim Rentsch wrote:
<snip>
> Problem: rng is a random number generator function that returns
> values uniformly distributed between 0 and rng_max, inclusive (so
> rng_max+1 possible values. Choose k+1 distinct random values (using
> the supplied function rng) in the range between 0 and n, inclusive
> (so n+1 possible values).

That rng_max is really an error since it introduces a double step
that does not exist in reality (if you can instantiate an rng for the
range [0,rng_max], then you can as well directly instantiate one
for the range [0,n]). The requirement indeed boils down to
generating k+1 random numbers in the range [0,n]. If your intent,
as I guess, was to have one explicitly code the transformation of
range, you should have asked for an rng that (as usual) returns
numbers in [0,1[.

> Of these k+1 distinct values, return the
> j'th value in ascending order (so for j=0 return the least value,
> for j=k return the largest value, etc).

I don't think better can be done than:
1. loop to generate the random numbers
1.*. insert sorted into a containing array (ascending)
2. return the j-th element of the array.

Julio