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

Groups > comp.lang.c > #168672

Re: Compute Unique Numbers in a Set

From Mike Terry <news.dead.person.stones@darjeeling.plus.com>
Newsgroups comp.lang.c
Subject Re: Compute Unique Numbers in a Set
Date 2022-12-28 01:08 +0000
Organization Aioe.org NNTP Server
Message-ID <tog4u9$c0s$1@gioia.aioe.org> (permalink)
References <todbqe$16sg$1@gioia.aioe.org> <874jtgn7ls.fsf@bsb.me.uk>

Show all headers | View raw

On 27/12/2022 16:18, Ben Bacarisse wrote:
> Albert <invalid@gmail.com> writes:
> 
>> Is this the best way to generate unique random numbers in a set of 6
>> numbers?
> 
> No, but it's a valiant attempt!
> 
> It has a few issues.  First, the number of chosen numbers (6) is
> hard-wired into the function as a repeated code pattern.  You want to
> avoid both repeated code and code the represents something that is,
> essentially, data.
> 
> You want to aim for a function that takes two numbers, the upper bound
> of the numbers that can be chosen and the number of number to be
> chosen.  Personally, I'd also pass a pointer to where the chosen numbers
> should be written.
> 
> But the biggest problem is the algorithm.  Unless the range of possible
> choices is vast (and in your case it is only 60) the best method is to
> run through this range, picking each number with the correct
> probability.
> 
> What is the probability that 1 should be chosen?  Well, it's 6/60.
> That's easy and if we have a function
> 
>    bool true_with_probability(int n, in m);
> 
> that returns true n out of m times we can add 1 to the collection (or in
> your case, just print 1) simply by calling true_with_probability(6, 60)
> in an if statement.
> 
> Now what is the probability that 2 (the next possible candidate) should
> be chosen?  Well that depends on what has gone before.  If we chose 1
> previously then we should choose 2 with probability 5/59, but if we did
> not, it should be with probability 6/59.
> 
> I wonder if you can see the pattern and turn it into code using
> variables.  You'll have parameters giving the range and the number of
> numbers to pick as well as local variables that track the number of
> numbers considered so far and the number of numbers chosen so far.
> 
> I'm happy to post code, but I think you should try for yourself first.
> 

This seems highly inefficient to me, IIUC.

We have a range of 60 numbers, and we only want 6 of them.  With your method, the expected number of 
random numbers we have to generate is, um, I think (60 - 54/7) ?  That's around 52.?  Everyone elses 
methods only have 6 random number generations, plus what seems to me a small overhead to avoid 
selecting a duplicate.  52 vs 6+smalloverhead ???


Regards,
Mike.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Compute Unique Numbers in a Set Albert <invalid@gmail.com> - 2022-12-26 23:45 +0000
  Re: Compute Unique Numbers in a Set "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2022-12-26 16:52 -0800
    Re: Compute Unique Numbers in a Set tTh <tth@none.invalid> - 2022-12-27 02:44 +0100
      Re: Compute Unique Numbers in a Set "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2022-12-27 13:35 -0800
  Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2022-12-26 20:47 -0500
    Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-27 15:57 +0000
      Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2022-12-27 11:16 -0500
        Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-27 16:59 +0000
          Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2022-12-27 12:24 -0500
            Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-27 17:53 +0000
              Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2022-12-27 13:50 -0500
                Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-27 20:08 +0000
                Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2022-12-27 15:31 -0500
                Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-28 02:57 +0000
                Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2022-12-27 23:02 -0500
                Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-29 02:06 +0000
                Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2022-12-28 23:42 -0500
                Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-29 12:26 +0000
  Re: Compute Unique Numbers in a Set Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-27 07:34 -0800
  Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-27 16:18 +0000
    Re: Compute Unique Numbers in a Set Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2022-12-28 01:08 +0000
      Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-12-28 03:30 +0000
    Re: Compute Unique Numbers in a Set Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-27 19:42 -0800
  Re: Compute Unique Numbers in a Set Manu Raju <MR@invalid.invalid> - 2022-12-27 18:11 +0000
  Re: Compute Unique Numbers in a Set antispam@math.uni.wroc.pl - 2022-12-28 01:32 +0000
    Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2022-12-27 21:13 -0500
      Re: Compute Unique Numbers in a Set Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-12-27 19:48 -0800
        Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2022-12-27 23:06 -0500
      Re: Compute Unique Numbers in a Set antispam@math.uni.wroc.pl - 2022-12-29 19:47 +0000
  Re: Compute Unique Numbers in a Set jak <nospam@please.ty> - 2022-12-28 11:28 +0100
  Re: Compute Unique Numbers in a Set Rosario19 <Ros@invalid.invalid> - 2023-01-01 21:06 +0100
    Re: Compute Unique Numbers in a Set Rosario19 <Ros@invalid.invalid> - 2023-01-02 06:43 +0100
  Re: Compute Unique Numbers in a Set gazelle@shell.xmission.com (Kenny McCormack) - 2023-01-01 23:19 +0000
    Re: Compute Unique Numbers in a Set jak <nospam@please.ty> - 2023-01-02 07:28 +0100
      Re: Compute Unique Numbers in a Set jak <nospam@please.ty> - 2023-01-02 08:48 +0100
      Re: Compute Unique Numbers in a Set Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-01-01 23:53 -0800
        Re: Compute Unique Numbers in a Set Öö Tiib <ootiib@hot.ee> - 2023-01-02 01:18 -0800
    Re: Compute Unique Numbers in a Set gazelle@shell.xmission.com (Kenny McCormack) - 2023-01-02 13:49 +0000
  Re: Compute Unique Numbers in a Set Bart <bc@freeuk.com> - 2023-01-02 12:27 +0000
  Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2023-01-02 12:13 -0500
    Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-02 17:31 +0000
      Re: Compute Unique Numbers in a Set Richard Damon <Richard@Damon-Family.org> - 2023-01-02 12:46 -0500
      Re: Compute Unique Numbers in a Set Siri Cruise <chine.bleu@yahoo.com> - 2023-01-02 18:54 -0800
      Re: Compute Unique Numbers in a Set Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-01-02 20:52 -0800
      Re: Compute Unique Numbers in a Set David Brown <david.brown@hesbynett.no> - 2023-01-03 09:01 +0100
      Re: Compute Unique Numbers in a Set Tim Rentsch <tr.17687@z991.linuxsc.com> - 2023-01-03 07:28 -0800
        Re: Compute Unique Numbers in a Set gazelle@shell.xmission.com (Kenny McCormack) - 2023-01-03 15:46 +0000
          Re: Compute Unique Numbers in a Set David Brown <david.brown@hesbynett.no> - 2023-01-03 18:19 +0100
  Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-08 03:48 +0100
    Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-08 04:18 +0100
    Re: Compute Unique Numbers in a Set gazelle@shell.xmission.com (Kenny McCormack) - 2023-01-08 03:48 +0000
      Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-08 05:12 +0100
        Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-08 06:01 +0100
          Re: Compute Unique Numbers in a Set Bart <bc@freeuk.com> - 2023-01-08 14:48 +0000
            Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-08 18:22 +0100
              Re: Compute Unique Numbers in a Set Bart <bc@freeuk.com> - 2023-01-08 17:46 +0000
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-09 04:58 +0100
                Re: Compute Unique Numbers in a Set Bart <bc@freeuk.com> - 2023-01-09 11:26 +0000
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-09 15:57 +0100
            Re: Compute Unique Numbers in a Set Bart <bc@freeuk.com> - 2023-01-08 17:34 +0000
              Re: Compute Unique Numbers in a Set Ike Naar <ike@sdf.org> - 2023-01-08 21:45 +0000
                Re: Compute Unique Numbers in a Set Bart <bc@freeuk.com> - 2023-01-08 23:13 +0000
                Re: Compute Unique Numbers in a Set "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-01-08 15:18 -0800
          Re: Compute Unique Numbers in a Set Paavo Helde <eesnimi@osa.pri.ee> - 2023-01-08 21:19 +0200
          Re: Compute Unique Numbers in a Set "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2023-01-09 12:03 +0100
            Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-09 17:42 +0100
              Re: Compute Unique Numbers in a Set Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2023-01-09 14:48 -0800
              Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-09 23:22 +0000
                Re: Compute Unique Numbers in a Set Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2023-01-09 18:28 -0800
                Re: Compute Unique Numbers in a Set Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2023-01-09 18:44 -0800
                Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-10 03:08 +0000
                Re: Compute Unique Numbers in a Set Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2023-01-09 19:19 -0800
                Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-10 17:30 +0000
                Re: Compute Unique Numbers in a Set Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2023-01-10 09:45 -0800
                Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-10 02:57 +0000
              Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-13 08:26 +0100
                Re: Compute Unique Numbers in a Set Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2023-01-13 03:32 -0800
                Re: Compute Unique Numbers in a Set gazelle@shell.xmission.com (Kenny McCormack) - 2023-01-13 12:21 +0000
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-13 14:11 +0100
                Re: Compute Unique Numbers in a Set gazelle@shell.xmission.com (Kenny McCormack) - 2023-01-13 13:55 +0000
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-13 15:02 +0100
                Re: Compute Unique Numbers in a Set gazelle@shell.xmission.com (Kenny McCormack) - 2023-01-13 14:17 +0000
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-15 16:06 +0100
                Re: Compute Unique Numbers in a Set Bart <bc@freeuk.com> - 2023-01-15 16:27 +0000
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-15 17:42 +0100
                Re: Compute Unique Numbers in a Set gazelle@shell.xmission.com (Kenny McCormack) - 2023-01-15 17:11 +0000
        Re: Compute Unique Numbers in a Set tTh <tth@none.invalid> - 2023-01-08 10:13 +0100
          Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-08 10:25 +0100
            Re: Compute Unique Numbers in a Set gazelle@shell.xmission.com (Kenny McCormack) - 2023-01-08 13:20 +0000
    Re: Compute Unique Numbers in a Set "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-01-08 13:09 -0800
  Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-09 02:37 +0000
  Re: Compute Unique Numbers in a Set John Forkosh <forkosh@panix.com> - 2023-01-15 02:49 +0000

csiph-web