Path: csiph.com!weretis.net!feeder8.news.weretis.net!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.programming
Subject: Programming exercise - choose_k_of_n_then_select()
Date: Sun, 29 Jan 2023 20:00:39 -0800
Organization: A noiseless patient Spider
Lines: 62
Message-ID: <86cz6wfz88.fsf@linuxsc.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: reader01.eternal-september.org; posting-host="fd425b27726ecb76a3994e723f0bd6b3"; logging-data="3305284"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/EzSnjodS4GK5Y+XKtCgj99D6Rl2/2E2A="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:5L+fjqdIQM08Td5zpAwod9zoxgw= sha1:+mmekLgS4j8MnhBeqvx9O3SmGvE=
Xref: csiph.com comp.programming:16354

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!