Groups | Search | Server Info | Keyboard shortcuts | Login | Register

Groups > comp.programming > #16357

Re: Programming exercise - choose_k_of_n_then_select()

Show all headers | View raw

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.

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