Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #168687
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Compute Unique Numbers in a Set |
| Date | 2022-12-29 12:26 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <87358yjsz4.fsf@bsb.me.uk> (permalink) |
| References | (9 earlier) <HCIqL.374481$GNG9.98817@fx18.iad> <874jtgkzft.fsf@bsb.me.uk> <CdPqL.95542$Tcw8.10688@fx10.iad> <87mt77j741.fsf@bsb.me.uk> <lV8rL.67445$t5W7.17482@fx13.iad> |
Richard Damon <Richard@Damon-Family.org> writes:
> On 12/28/22 9:06 PM, Ben Bacarisse wrote:
>> Richard Damon <Richard@Damon-Family.org> writes:
>>
>>> On 12/27/22 9:57 PM, Ben Bacarisse wrote:
>>>> Richard Damon <Richard@Damon-Family.org> writes:
>>>>
>>>>> On 12/27/22 3:08 PM, Ben Bacarisse wrote:
>>>>>> Richard Damon <Richard@Damon-Family.org> writes:
>>>>>>
>>>>>>> On 12/27/22 12:53 PM, Ben Bacarisse wrote:
>>>>>>>> Richard Damon <Richard@Damon-Family.org> writes:
>>>>>>>>
>>>>>>>>> On 12/27/22 11:59 AM, Ben Bacarisse wrote:
>>>>>>>>>> Richard Damon <Richard@Damon-Family.org> writes:
>>>>>>>>>>
>>>>>>>>>>> On 12/27/22 10:57 AM, Ben Bacarisse wrote:
>>>>>>>>>>>> Richard Damon <Richard@Damon-Family.org> writes:
>>>>>>>>>>>>
>>>>>>>>>>>>> On 12/26/22 6:45 PM, Albert wrote:
>>>>>>>>>>>>>> Is this the best way to generate unique random numbers in a set of 6
>>>>>>>>>>>>>> numbers?
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> An alternate way to generate numbers without repeat, and avoid
>>>>>>>>>>>>> recalling the random number generator, is first generate the number
>>>>>>>>>>>>> between 0 and N-1,
>>>>>>>>>>>>>
>>>>>>>>>>>>> Then generate the second number between 0 and N-2, and if the result
>>>>>>>>>>>>> is greater than or equal the first number, increment it.
>>>>>>>>>>>>>
>>>>>>>>>>>>> Then generate the third number between 0 and N-3, and if the result is
>>>>>>>>>>>>> greater than or equal to the first number, increment it. THen if it is
>>>>>>>>>>>>> greater than or equal to the second number, increment it.
>>>>>>>>>>>>>
>>>>>>>>>>>>> Just keep repeating the pattern with smaller and smaller ranges, and
>>>>>>>>>>>>> compare to the previous numbers in order, and increment if the value
>>>>>>>>>>>>> at that point is greater than or equoal.
>>>>>>>>>>>> I don't see how this does the job at all. For example, when picking 3
>>>>>>>>>>>> from, say, [0,5] we might pick 2 and then 1. Now if the third choice is
>>>>>>>>>>>> 1 it is not equal to 2 (so no increment) but it is equal to 1 so
>>>>>>>>>>>> increment to 2.
>>>>>>>>>>>
>>>>>>>>>>> As I think about it, if you increment, you need to restart the scan
>>>>>>>>>>> with the beginning number, but not repeat a test. Another way is have
>>>>>>>>>>> a sorted list of picks and work smallest to largest.
>>>>>>>>>>>
>>>>>>>>>>> So:
>>>>>>>>>>>
>>>>>>>>>>> #1
>>>>>>>>>>> From [0, 5] get 2
>>>>>>>>>>>
>>>>>>>>>>> #2
>>>>>>>>>>> From [0, 4] get 1
>>>>>>>>>>> 1 not >= 2 so ok.
>>>>>>>>>>>
>>>>>>>>>>> #3
>>>>>>>>>>>
>>>>>>>>>>> From [0, 3] get 1
>>>>>>>>>>> 1 not >= 2 so next
>>>>>>>>>>> 1 IS >= 1 so make 2 and restart
>>>>>>>>>>> 1 >= 2 so make 3
>>>>>>>>>> Presumably "2 >= 2 so make 3"
>>>>>>>>>>
>>>>>>>>>>> don't repeat test 2.
>>>>>>>>>> Now you just get highly biased results (if I've got then hang of it).
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> No, it is unbiased, we skip the test of the second number, as that
>>>>>>>>> rule was already used for this number.
>>>>>>>>
>>>>>>>> What's the algorithm, then? My attempt to code it from your description
>>>>>>>> must have gone wrong.
>>>>>>>
>>>>>>> You choose a random number based on the number of UNCHOSEN numbers
>>>>>>> left.
>>>>>> Can you give the algorithm using some pseudo code?
>>>>>>
>>>>>>> since they weren't all the lowest numbers, you increase the value by
>>>>>>> one for every chosen value that is less than or equal to the number
>>>>>>> picked (including after any other increases).
>>>>>> Surely it's a few lines of pseudo code. I'm getting lost in the words.
>>>>>
>>>>> simplest version, which keeps a temp sorted array.
>>>>>
>>>>> function non_repeating_random_range(
>>>>> int npick, // number of picks to make
>>>>> int nchoice, // range of choices
>>>>> int* randoms): // array to return the answers in
>>>>>
>>>>> int ordered_list[npick]; // List of picks in acending order
>>>>> for i in 0 to npick-1
>>>>> random = random_number(nchoice-i); // Random unpicked slot
>>>>> for element in urdered_list:
>>>>> if random >= element: random++
>>>>> else break from loop
>>>>> *randoms++ = random;
>>>>> insert random into ordered_list
>>>> OK, I see what you were getting at.
>>>> That seems a little more fussy than Floyd's algorithm using a set:
>>>> set<int> S = {}
>>>> for j = nchoice - npick + 1 to nchoice
>>>> r = random_int(j) + 1
>>>> insert into S (if r in S then j else r)
>>>
>>> Because his method first only generates a "Set", which appears to not
>>> remember the order of insertion
>> I don't know what this "because" relates to.
>
> Do you understand the difference between a "List" and a "Set"
Seriously?
> A List has the POTENTIAL of dupicate entries, and keeps track of order.
>
> A Set (normally) can't hold duplicate entries, and doesn't keep track of order.
>
> The Set {1, 2, 3, 4} is the exact same Set as {4, 3, 2, 1}
> but the list [1, 2, 3, 4] isn't the same as [4, 3, 2, 1]
>
> Floyd's program give just a random Set of numbers (perhaps becuase the
> OP used the term "Set" in an informal manner to express his
> problem. It does NOT generate a uniform answer if the order was
> important.
Of course I understand all that.
>>> He is generating a random combination, not a random (partial)
>>> permutation. The original program seemed to make a distinction. The
>>> question comes is the answer 1, 2, 3, 4, 5 different than 5, 4, 3, 2,
>>> 1 ?
>>>
>>> If his set tries to remember order, then the first element CAN'T be
>>> from the whole set, as the random_int for that isn't from the whold
>>> nchoice option.
>> I'm lost again.
>>
>
> Floyd's program is based on math that assumes it doesn't matter what
> order the numbers are in, that the results are just considered a "Set"
> that doesn't consider the order of the numbers to be important.
>
> In Math, these sorts of assortments are often called combitorals. In
> combitorial math, STAR and RATS are "The Same" as they use the same
> SET of letters, so they are the same results of selecting 4 letters
> out of the alphabet.
>
> Permutations keep track of order, so STAR and RATS are different answers.
>
> A simple point to note, Floyd's generator when taking 6 picks out of
> 59 symbols will NEVER chose the number 59 as its first pick, so it
> does NOT generate permutations with uniform distribution. In fact, the
> ONLY pick that can have the value of 59 will be the last one, but that
> one will have a 6/59 chance of being 59.
>
> When treated as a combination, so order doesn't matter, the sets do
> turn out to be uniformly distrbuted.
>
> Ultimately, the question comes did the OP think order mattered or not.
So you thought I might not know some basic things about a sets and lists
and there did not know what the algorithm I posted did? Surely you
could just have said you thought OP wanted a uniform "perm" and I seemed
to have assumed they only wanted a uniform choice?
--
Ben.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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