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

Groups > comp.lang.c++ > #88569

Re: Compute Unique Numbers in a Set

From Muttley@dastardlyhq.com
Newsgroups comp.lang.c++
Subject Re: Compute Unique Numbers in a Set
Date 2023-01-17 17:16 +0000
Organization Aioe.org NNTP Server
Message-ID <tq6l4j$1sr4$1@gioia.aioe.org> (permalink)
References (18 earlier) <tq5prq$1u45$1@gioia.aioe.org> <tq66tg$38bg3$1@dont-email.me> <3d614abf-c869-4288-8837-2a7e9c11050bn@googlegroups.com> <tq6i65$b6g$1@gioia.aioe.org> <f9d7af32-c89e-4f03-968c-0c3d67a0cdd2n@googlegroups.com>

Show all headers | View raw

On Tue, 17 Jan 2023 09:08:12 -0800 (PST)
Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
>On Tuesday, 17 January 2023 at 16:25:56 UTC, Mut...@dastardlyhq.com wrote:
>> Just out of interest, what would be a better way? You could randomly select 
>> elements in a container then delete that particular element so it doesn't
>get 
>> used again but I'm not sure that would be very efficient beyond single digit 
>
>> container sizes. Ditto starting at a random point in the container and
>walking 
>> it in a random direction until you find an unused element.
>>
>You have the range 0 to N-1 to choose M unique elements from.
>Pick a single element x using a unifrom random number. That now gives
>us two ranges, 0 to x-1 and x+1 to N-1. And M-1 numbers left to pick.
>
>The number we need to pick from each range is given by the hypergeometric
>distribution. We have x "good" balls and N - x - 2 "bad" balls in an urn, and
>we withdraw M-1 balls. The number of "good" balls we draw tells us how many
>elemets to distribute to the first half of the range. The remainder of the
>elements
> we choose from the second half of the range.
>Then it's just recursive, with the range splitting on a random elemnet each
>level.
>
>You cna write a generator for numbers with a hypergeometric distribution
>naively
>and quite simply by taking M random numbers. Or you can do it in a far more
>complicated
>way by calculating the cumulative distribution function. If you do it the
>naive way,
>the algorithm is O(M log M) (M calls to the uniform function on each level,
>and log M 
>levels of recursion). If you do it the complicated way you can improve on that.

Probably looks good on a whiteboard but there's a lot of shifting stuff
about going on there so I doubt it'll be any faster (or more random) than 
simply doing random walks of an array until you find an unused element. But 
then its obviously based on the same algo as quicksort and selecting the 
optimal sorting function is a black art when copy costs vs comparison costs 
are factored in.

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

Thread

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 Tim Woodall <news001@woodall.me.uk> - 2023-01-13 06:35 +0000
              Re: Compute Unique Numbers in a Set Tim Woodall <news001@woodall.me.uk> - 2023-01-13 06:39 +0000
  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 Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-08 19:20 +0000
  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 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-10 05:11 -0800
        Re: Compute Unique Numbers in a Set Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2023-01-10 05:19 -0800
      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 Öö Tiib <ootiib@hot.ee> - 2023-01-13 03:26 -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 Ralf Goertz <me@myprovider.invalid> - 2023-01-15 16:47 +0100
            Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-15 17:13 +0100
            Re: Compute Unique Numbers in a Set Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2023-01-15 08:57 -0800
              Re: Compute Unique Numbers in a Set Ralf Goertz <me@myprovider.invalid> - 2023-01-16 09:46 +0100
                Re: Compute Unique Numbers in a Set Ralf Goertz <me@myprovider.invalid> - 2023-01-16 10:21 +0100
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-16 13:35 +0100
                Re: Compute Unique Numbers in a Set Ralf Goertz <me@myprovider.invalid> - 2023-01-16 14:46 +0100
                Re: Compute Unique Numbers in a Set Ralf Goertz <me@myprovider.invalid> - 2023-01-16 14:42 +0100
                Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-16 16:38 +0000
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-16 21:06 +0100
                Re: Compute Unique Numbers in a Set Ralf Goertz <me@myprovider.invalid> - 2023-01-17 09:19 +0100
                Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-17 09:30 +0000
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-17 14:14 +0100
                Re: Compute Unique Numbers in a Set Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2023-01-17 07:48 -0800
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-17 16:49 +0100
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-17 17:32 +0100
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-17 19:24 +0100
                Re: Compute Unique Numbers in a Set Ralf Goertz <me@myprovider.invalid> - 2023-01-17 17:31 +0100
                Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-17 17:10 +0000
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-17 18:18 +0100
                Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-18 09:23 +0000
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-18 13:31 +0100
                Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-18 16:16 +0000
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-18 17:20 +0100
                Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-18 16:24 +0000
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-18 17:59 +0100
                Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-18 17:14 +0000
                Re: Compute Unique Numbers in a Set Bonita Montero <Bonita.Montero@gmail.com> - 2023-01-18 18:23 +0100
                Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-19 09:31 +0000
                Re: Compute Unique Numbers in a Set "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-01-17 12:48 -0800
                Re: Compute Unique Numbers in a Set scott@slp53.sl.home (Scott Lurndal) - 2023-01-17 21:21 +0000
                Re: Compute Unique Numbers in a Set "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-01-17 13:29 -0800
                Re: Compute Unique Numbers in a Set Paul N <gw7rib@aol.com> - 2023-01-18 06:50 -0800
                Re: Compute Unique Numbers in a Set "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2023-01-18 11:59 -0800
                Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-17 16:25 +0000
                Re: Compute Unique Numbers in a Set Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2023-01-17 09:08 -0800
                Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-17 17:16 +0000
                Re: Compute Unique Numbers in a Set Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-17 17:32 +0000
                Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-18 09:23 +0000
                Re: Compute Unique Numbers in a Set gazelle@shell.xmission.com (Kenny McCormack) - 2023-01-18 12:26 +0000
                Re: Compute Unique Numbers in a Set Muttley@dastardlyhq.com - 2023-01-18 16:09 +0000
          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 Tim Woodall <news001@woodall.me.uk> - 2023-01-13 06:32 +0000
    Re: Compute Unique Numbers in a Set Öö Tiib <ootiib@hot.ee> - 2023-01-13 05:04 -0800

csiph-web