From: tr.17687@z991.linuxsc.com   
      
   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!   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)