Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #16356

Re: Programming exercise - choose_k_of_n_then_select()

Show all headers | View raw

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?

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Programming exercise - choose_k_of_n_then_select() Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-01-29 20:00 -0800
  Re: Programming exercise - choose_k_of_n_then_select() Paul N <gw7rib@aol.com> - 2023-01-30 06:01 -0800
    Re: Programming exercise - choose_k_of_n_then_select() Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-01-30 07:48 -0800
    Re: Programming exercise - choose_k_of_n_then_select() c186282 <c186282@nnada.net> - 2025-06-13 23:18 -0400
  Re: Programming exercise - choose_k_of_n_then_select() Julio Di Egidio <julio@diegidio.name> - 2023-01-31 06:14 -0800
    Re: Programming exercise - choose_k_of_n_then_select() Y A <air000000000000@ya.ee> - 2023-02-10 06:38 -0800

csiph-web