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

Groups > comp.programming > #16354 > unrolled thread

Programming exercise - choose_k_of_n_then_select()

Back to article view | Back to comp.programming

Contents

  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

#16354 — Programming exercise - choose_k_of_n_then_select()

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!

[toc] | [next] | [standalone]

#16356

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?

[toc] | [prev] | [next] | [standalone]

#16357

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.

[toc] | [prev] | [next] | [standalone]

#16788

On 1/30/23 9:01 AM, Paul N wrote:
> 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?

   Note that 'randomness' is impressively difficult to
   achieve using CPUs. And yes, in theory, you could get
   a lot of the SAME number. CPU approaches tend to use
   rules to get the NEXT 'random' number - which CAN be
   exploited by evil people with tera/peta-FLOPS and
   now 'AI' to throw at the problem, finding a pattern
   in supposed 'randomness'.

   Using some kind of quantum/quantum-like 'noise' as an
   element in the equation is usually the best. Radio
   "static", for example, or combined thermal readings
   or delay stats from several system chips. There are
   'randomness generator' chips. None of these methods
   are 'perfect', but often 'better' is good enough.

   Note the use of 'hashing' for things like database
   files. This was especially relevant in the days of
   slow CPUs and mechanical storage media. The 'random'
   hash code would let you zero-in on files quickly,
   as opposed to searching through one huge - maybe
   too huge - file. Also made search times more predictable.
   More than one record might get the same hash code, but
   it got you CLOSE. Those hashes weren't really "random",
   but 'good enough'.

[toc] | [prev] | [next] | [standalone]

#16359

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

[toc] | [prev] | [next] | [standalone]

#16402

Have You visited: http://meetupplaceforeveryone.atwebpages.com/a.php

and others:

https://groups.google.com/g/airplane/c/dNQxZmPVkbk


?






On Tuesday, January 31, 2023 at 4:14:15 PM UTC+2, Julio Di Egidio wrote:
> 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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web