Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #168644 > unrolled thread
| Started by | Albert <invalid@gmail.com> |
|---|---|
| First post | 2022-12-26 23:45 +0000 |
| Last post | 2023-01-15 02:49 +0000 |
| Articles | 20 on this page of 92 — 22 participants |
Back to article view | Back to comp.lang.c
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
Page 1 of 5 [1] 2 3 4 5 Next page →
| From | Albert <invalid@gmail.com> |
|---|---|
| Date | 2022-12-26 23:45 +0000 |
| Subject | Compute Unique Numbers in a Set |
| Message-ID | <todbqe$16sg$1@gioia.aioe.org> |
Is this the best way to generate unique random numbers in a set of 6
numbers?
<******************************************************>
void generateNumbers()
{
int val1, val2, val3, val4, val5, val6;
val1 = rand() % 59 + 1;
printf("%4d", val1);
val2 = rand() % 59 + 1;
while (val2 == val1)
{
val2 = rand() % 59 + 1;
}
printf("%4d", val2);
val3 = rand() % 59 + 1;
while (val3 == val1 || val3 == val2)
{
val3 = rand() % 59 + 1;
}
printf("%4d", val3);
val4 = rand() % 59 + 1;
while (val4 == val1 || val4 == val2 || val4 == val3)
{
val4 = rand() % 59 + 1;
}
printf("%4d", val4);
val5 = rand() % 59 + 1;
while (val5 == val1 || val5 == val2 || val5 == val3 || val5 == val4)
{
val5 = rand() % 59 + 1;
}
printf("%4d", val5);
val6 = rand() % 59 + 1;
while (val6 == val1 || val6 == val2 || val6 == val3 || val6 == val4
|| val6 == val5)
{
val6 = rand() % 59 + 1;
}
printf("%4d", val6);
printf("\n");
}
<******************************************************>
The main prog using this function:
#include <stdio.h>
#include <stdlib.h>
#include<windows.h>
int main(void)
{
for (int i = 0; i < 100; i++)
{
generateNumbers();
Sleep(1000);
}
return 0;
}
[toc] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2022-12-26 16:52 -0800 |
| Message-ID | <todfke$3dspq$1@dont-email.me> |
| In reply to | #168644 |
On 12/26/2022 3:45 PM, Albert wrote:
> Is this the best way to generate unique random numbers in a set of 6
> numbers?
[...]
Is this homework?
__________________
bool
unique(
unsigned long* p,
unsigned long t,
std::size_t n
) {
for (unsigned long i = 0; i < n; ++i)
{
if (p[i] == t) return false;
}
return true;
}
void
gen()
{
std::size_t n = 6;
unsigned long p[6] = { 0 };
std::srand(std::time(nullptr));
for (std::size_t i = 0; i < n; ++i)
{
unsigned long r = (std::rand() % 6) + 1;
if (! unique(p, r, i))
{
--i;
continue;
}
p[i] = r;
std::cout << p[i] << ", ";
}
}
__________________
I just typed that code out on the fly, sorry for any typos.
[toc] | [prev] | [next] | [standalone]
| From | tTh <tth@none.invalid> |
|---|---|
| Date | 2022-12-27 02:44 +0100 |
| Message-ID | <todim7$13rd$1@news.gegeweb.eu> |
| In reply to | #168645 |
On 12/27/22 01:52, Chris M. Thomasson wrote:
> On 12/26/2022 3:45 PM, Albert wrote:
>> Is this the best way to generate unique random numbers in a set of 6
>> numbers?
> [...]
>
> Is this homework?
> std::size_t n
This is not valid C.
--
+------------------------------------------------------------------+
| http://la.buvette.org/musique/xmas/song10.mp3 |
| https://danstonchat.com/1138.html |
+------------------------------------------------------------------+
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2022-12-27 13:35 -0800 |
| Message-ID | <tofoem$3nhm2$4@dont-email.me> |
| In reply to | #168646 |
On 12/26/2022 5:44 PM, tTh wrote: > On 12/27/22 01:52, Chris M. Thomasson wrote: >> On 12/26/2022 3:45 PM, Albert wrote: >>> Is this the best way to generate unique random numbers in a set of 6 >>> numbers? >> [...] >> >> Is this homework? > >> std::size_t n > > This is not valid C. > Yeah, I know. I thought it might be able to help in some way. I have been writing a lot of C++ lately, so, it's on my mind, so to speak.
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2022-12-26 20:47 -0500 |
| Message-ID | <r8sqL.106906$iU59.104545@fx14.iad> |
| In reply to | #168644 |
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. If you put the numbers in an array, this becomes a concise routing with two nested loops, the outer loop creating new numbers, and the inner loop incrementing if greater than or equal to a previous picked number.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-12-27 15:57 +0000 |
| Message-ID | <87a638n8kj.fsf@bsb.me.uk> |
| In reply to | #168647 |
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. > If you put the numbers in an array, this becomes a concise routing > with two nested loops, the outer loop creating new numbers, and the > inner loop incrementing if greater than or equal to a previous picked > number. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2022-12-27 11:16 -0500 |
| Message-ID | <DTEqL.146517$gGD7.19214@fx11.iad> |
| In reply to | #168653 |
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 don't repeat test 2. > >> If you put the numbers in an array, this becomes a concise routing >> with two nested loops, the outer loop creating new numbers, and the >> inner loop incrementing if greater than or equal to a previous picked >> number. >
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-12-27 16:59 +0000 |
| Message-ID | <87sfh0lr50.fsf@bsb.me.uk> |
| In reply to | #168656 |
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). -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2022-12-27 12:24 -0500 |
| Message-ID | <iTFqL.10904$OD18.573@fx08.iad> |
| In reply to | #168659 |
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. The first number is chosen from the N available Numbers. The second number is chosen from the N-1 available, the adjustments are done to map the value 0 to N-2 to the N-1 numbers that have not be chosen yet, so we need to increase it for every already chose number that is below the slot we chose. And so on. This method is optimised assuming you are selecting a small percentage of the possible values. If you are selecting a random ordering of all (or most) of the numbers, shuffling techniques are likely quicker.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-12-27 17:53 +0000 |
| Message-ID | <87h6xglom6.fsf@bsb.me.uk> |
| In reply to | #168660 |
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. > This method is optimised assuming you are selecting a small percentage > of the possible values. If you are selecting a random ordering of all > (or most) of the numbers, shuffling techniques are likely quicker. Optimised in terms of what? It seems to include a nested search, but I may not be following the algorithm. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2022-12-27 13:50 -0500 |
| Message-ID | <Y7HqL.20387$wfQc.14603@fx43.iad> |
| In reply to | #168662 |
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. 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). This can be done by either keeping a temporary sorted list, or scanning through the list, repeating if you adjust, but needing to keep track so you don't use a number twice, or repeated scan till you find a stable value of the count of occurances of previously chosen numbers <= random number + the (previous) count of occurance of previously chosen numbers > >> This method is optimised assuming you are selecting a small percentage >> of the possible values. If you are selecting a random ordering of all >> (or most) of the numbers, shuffling techniques are likely quicker. > > Optimised in terms of what? It seems to include a nested search, but I > may not be following the algorithm. > The optimization is first with respect to the number of calls to the random number generator, which is presumed to be at least mildly expensive. Perhaps if using a very cheap generator, like the Linear Congruential Generator (multiply/add/mod) this doesn't apply, Yes, either you need additional memory for the temp sorted list, or the need for repeated scans through the list of previously chosen numbers, but if the number of picks is small compared to the size of the numbers being picked, this is a small factor, if the random number generator is mildly expensive, and the naive method of the OP still requires at least one scan through the list per pick (and gets repeated on duplicates). If getting a complete (or nearly complete) permutation, shuffling can give you a strictly O(N) solution.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-12-27 20:08 +0000 |
| Message-ID | <87bknolie2.fsf@bsb.me.uk> |
| In reply to | #168665 |
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. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2022-12-27 15:31 -0500 |
| Message-ID | <HCIqL.374481$GNG9.98817@fx18.iad> |
| In reply to | #168666 |
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
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-12-28 02:57 +0000 |
| Message-ID | <874jtgkzft.fsf@bsb.me.uk> |
| In reply to | #168667 |
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)
--
Ben.
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2022-12-27 23:02 -0500 |
| Message-ID | <CdPqL.95542$Tcw8.10688@fx10.iad> |
| In reply to | #168675 |
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
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.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-12-29 02:06 +0000 |
| Message-ID | <87mt77j741.fsf@bsb.me.uk> |
| In reply to | #168680 |
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.
> 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.
--
Ben.
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2022-12-28 23:42 -0500 |
| Message-ID | <lV8rL.67445$t5W7.17482@fx13.iad> |
| In reply to | #168684 |
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"
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.
>
>> 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.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-12-29 12:26 +0000 |
| Message-ID | <87358yjsz4.fsf@bsb.me.uk> |
| In reply to | #168686 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2022-12-27 07:34 -0800 |
| Message-ID | <861qokx3ly.fsf@linuxsc.com> |
| In reply to | #168644 |
Albert <invalid@gmail.com> writes:
> Is this the best way to generate unique random numbers in a set of 6
> numbers?
[..edited to limit line length..]
> <******************************************************>
>
> void generateNumbers()
> {
> int val1, val2, val3, val4, val5, val6;
>
> val1 = rand() % 59 + 1;
> printf("%4d", val1);
>
> val2 = rand() % 59 + 1;
> while (val2 == val1)
> {
> val2 = rand() % 59 + 1;
> }
> printf("%4d", val2);
>
> val3 = rand() % 59 + 1;
> while (val3 == val1 || val3 == val2)
> {
> val3 = rand() % 59 + 1;
> }
> printf("%4d", val3);
>
> val4 = rand() % 59 + 1;
> while (val4 == val1 || val4 == val2 || val4 == val3)
> {
> val4 = rand() % 59 + 1;
> }
> printf("%4d", val4);
>
> val5 = rand() % 59 + 1;
> while (
> val5 == val1 || val5 == val2 ||
> val5 == val3 || val5 == val4
> )
> {
> val5 = rand() % 59 + 1;
> }
> printf("%4d", val5);
>
> val6 = rand() % 59 + 1;
> while (
> val6 == val1 || val6 == val2 || val6 == val3 ||
> val6 == val4 || val6 == val5
> )
> {
> val6 = rand() % 59 + 1;
> }
> printf("%4d", val6);
> printf("\n");
> }
> <******************************************************>
>
> The main prog using this function:
> #include <stdio.h>
> #include <stdlib.h>
> #include<windows.h>
>
> int main(void)
> {
> for (int i = 0; i < 100; i++)
> {
> generateNumbers();
> Sleep(1000);
> }
> return 0;
> }
Some problems:
1. There is no seeding of the random number generator.
2. The rand() function is generally best avoided, because the
random numbers it produces can be (and at least sometimes
are) of very low quality.
3. Using a simple modulo ('% 59') has a bias towards low
numbers. Normally what is wanted is a uniform distribution,
but the numbers produced above will be not quite uniform.
4. The technique of testing to see if there are matches to
previous numbers is clunky, and it can be avoided easily
by using a small array.
Some key functionalities (mixture of C and pseudo-code):
First, establish an array with the values you are interested in:
#define LARGEST_VALUE 59
static unsigned char values_1_to_whatever[ LARGEST_VALUE ];
for( i from 0 to LARGEST_VALUE-1 ){
values_1_to_whatever[ i ] = i+1;
}
Second, function to produce distict numbers:
void
produce_some_random_values( unsigned how_many ){
unsigned i, j;
for( i = 0; i < how_many; i++ ){
unsigned k = uniform_random_less_than( LARGEST_VALUE - i );
exchange values_1_to_whatever[i] and values_1_to_whatever[i+k];
}
/* results are in values_1_to_whatever[x] ... */
/* where x is in [ 0 .. how_many ) */
}
Third, function to produce unbiased uniform random number in
suitable range:
unsigned
uniform_random_less_than( unsigned k ){
unsigned r;
unsigned biggest = largest_possible_random_value();
while( biggest%k != k-1 ) biggest -= 1;
do {
r = next_random_value();
} while( r > biggest );
return r % k;
}
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-12-27 16:18 +0000 |
| Message-ID | <874jtgn7ls.fsf@bsb.me.uk> |
| In reply to | #168644 |
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.
> <******************************************************>
>
> void generateNumbers()
> {
> int val1, val2, val3, val4, val5, val6;
>
> val1 = rand() % 59 + 1;
> printf("%4d", val1);
>
> val2 = rand() % 59 + 1;
> while (val2 == val1)
> {
> val2 = rand() % 59 + 1;
> }
> printf("%4d", val2);
>
> val3 = rand() % 59 + 1;
> while (val3 == val1 || val3 == val2)
> {
> val3 = rand() % 59 + 1;
> }
> printf("%4d", val3);
>
> val4 = rand() % 59 + 1;
> while (val4 == val1 || val4 == val2 || val4 == val3)
> {
> val4 = rand() % 59 + 1;
> }
> printf("%4d", val4);
>
> val5 = rand() % 59 + 1;
> while (val5 == val1 || val5 == val2 || val5 == val3 || val5 == val4)
> {
> val5 = rand() % 59 + 1;
> }
> printf("%4d", val5);
>
> val6 = rand() % 59 + 1;
> while (val6 == val1 || val6 == val2 || val6 == val3 || val6 == val4
> || val6 == val5)
> {
> val6 = rand() % 59 + 1;
> }
> printf("%4d", val6);
> printf("\n");
> }
> <******************************************************>
>
> The main prog using this function:
> #include <stdio.h>
> #include <stdlib.h>
> #include<windows.h>
>
> int main(void)
> {
> for (int i = 0; i < 100; i++)
> {
> generateNumbers();
> Sleep(1000);
> }
> return 0;
> }
--
Ben.
[toc] | [prev] | [next] | [standalone]
Page 1 of 5 [1] 2 3 4 5 Next page →
Back to top | Article view | comp.lang.c
csiph-web