On Tuesday, 10 January 2023 at 02:28:48 UTC, Malcolm McLean wrote:
> On Monday, 9 January 2023 at 23:22:24 UTC, Ben Bacarisse wrote:
> > Bonita Montero <Bonita....@gmail.com> writes:
> >
> > > Am 09.01.2023 um 12:03 schrieb Alf P. Steinbach:
> > >
> > >> When n is large and is near or equal to the number of possible
> > >> values, this loop becomes inefficient: for the last number you can
> > >> expect on average n iterations to find that number, because each call
> > >> of uid has a 1/n chance of finding it.
> > >
> > > I know that the loop becomes inefficient then, but tell me a better
> > > alternative algorithm.
> > An alternative that works well in those cases (and in some others) has
> > already been described where each candidate is chosen with the
> > appropriate probability. I originally set it out as an exercises since
> > I thought the OP was doing homework, but the gist of it was explained.
> > > You'd have a list of eligible numbers and
> > > randomly chose one of them. That would also take a lot of time to
> > > remove the number from the list.
> > No need:
> >
> > void choose(int choose_n, int from_m, int *output)
> > {
> > for (int i = 0, j = 0; j < choose_n; i++)
> > if (true_with_probability(choose_n - j, from_m - i))
> > output[j++] = i + 1;
> > }
> >
> > Obviously using one would not use this to choose 3 numbers from a set of
> > millions!
> >
> We're choosing M values from N.
> If we choose a random member, i, then we have two sets, 0 to i-1, and i+1 to N-1,
> and M-1 values left to choose.
> So basically we would expect a binomial distribution, with each remaining value
> having an (i-1)/(N-1) chance of ending up in the first set. We then recurse.
> However the whole point of the problem is that the distribution is discrete, and this
> isn't quite correct, because we could end up with more values to choose than
> members of the set. This would happen very rarely if N is large in relation to M,
> but it could happen.
> I'm not quite sure how to correct for this.
>
Ah. It's the hypergeometric distribution. Very messy.

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On Monday, 9 January 2023 at 23:22:24 UTC, Ben Bacarisse wrote:
>> Bonita Montero <Bonita....@gmail.com> writes:
>>
>> > Am 09.01.2023 um 12:03 schrieb Alf P. Steinbach:
>> >
>> >> When n is large and is near or equal to the number of possible
>> >> values, this loop becomes inefficient: for the last number you can
>> >> expect on average n iterations to find that number, because each call
>> >> of uid has a 1/n chance of finding it.
>> >
>> > I know that the loop becomes inefficient then, but tell me a better
>> > alternative algorithm.
>> An alternative that works well in those cases (and in some others) has
>> already been described where each candidate is chosen with the
>> appropriate probability. I originally set it out as an exercises since
>> I thought the OP was doing homework, but the gist of it was explained.
>> > You'd have a list of eligible numbers and
>> > randomly chose one of them. That would also take a lot of time to
>> > remove the number from the list.
>> No need:
>>
>> void choose(int choose_n, int from_m, int *output)
>> {
>> for (int i = 0, j = 0; j < choose_n; i++)
>> if (true_with_probability(choose_n - j, from_m - i))
>> output[j++] = i + 1;
>> }
>>
>> Obviously using one would not use this to choose 3 numbers from a set of
>> millions!
>>
> We're choosing M values from N.

This function chooses "choose_n" from "from_m". Not great names I
admit...

> If we choose a random member, i, then we have two sets, 0 to i-1, and
> i+1 to N-1, and M-1 values left to choose.
> So basically we would expect a binomial distribution, with each
> remaining value having an (i-1)/(N-1) chance of ending up in the first
> set. We then recurse.
> However the whole point of the problem is that the distribution is>
> discrete, and this isn't quite correct, because we could end up with
> more values to choose than members of the set. This would happen very
> rarely if N is large in relation to M, but it could happen. I'm not
> quite sure how to correct for this.

I can't follow this. Do you think there is a problem with the
algorithm?

Every candidate is considered, and i is chosen with a probability that
takes account of how many numbers have already been selected (j) and how
many candidates remain (from_m - i).

--
Ben.

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On Tuesday, 10 January 2023 at 02:28:48 UTC, Malcolm McLean wrote:
>> On Monday, 9 January 2023 at 23:22:24 UTC, Ben Bacarisse wrote:
>> > Bonita Montero <Bonita....@gmail.com> writes:
>> >
>> > > Am 09.01.2023 um 12:03 schrieb Alf P. Steinbach:
>> > >
>> > >> When n is large and is near or equal to the number of possible
>> > >> values, this loop becomes inefficient: for the last number you can
>> > >> expect on average n iterations to find that number, because each call
>> > >> of uid has a 1/n chance of finding it.
>> > >
>> > > I know that the loop becomes inefficient then, but tell me a better
>> > > alternative algorithm.
>> > An alternative that works well in those cases (and in some others) has
>> > already been described where each candidate is chosen with the
>> > appropriate probability. I originally set it out as an exercises since
>> > I thought the OP was doing homework, but the gist of it was explained.
>> > > You'd have a list of eligible numbers and
>> > > randomly chose one of them. That would also take a lot of time to
>> > > remove the number from the list.
>> > No need:
>> >
>> > void choose(int choose_n, int from_m, int *output)
>> > {
>> > for (int i = 0, j = 0; j < choose_n; i++)
>> > if (true_with_probability(choose_n - j, from_m - i))
>> > output[j++] = i + 1;
>> > }
>> >
>> > Obviously using one would not use this to choose 3 numbers from a set of
>> > millions!
>> >
>> We're choosing M values from N.
>> If we choose a random member, i, then we have two sets, 0 to i-1, and i+1 to N-1,
>> and M-1 values left to choose.
>> So basically we would expect a binomial distribution, with each remaining value
>> having an (i-1)/(N-1) chance of ending up in the first set. We then recurse.
>> However the whole point of the problem is that the distribution is discrete, and this
>> isn't quite correct, because we could end up with more values to choose than
>> members of the set. This would happen very rarely if N is large in relation to M,
>> but it could happen.
>> I'm not quite sure how to correct for this.
>>
> Ah. It's the hypergeometric distribution. Very messy.

What quantity are you referring to? There may be something that has a
messy distribution in all of this but (a) I don't know what quantity you
are talking about and (b) I don't think it matters.

--
Ben.

On Tuesday, 10 January 2023 at 03:08:40 UTC, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>
> > On Tuesday, 10 January 2023 at 02:28:48 UTC, Malcolm McLean wrote:
> >> On Monday, 9 January 2023 at 23:22:24 UTC, Ben Bacarisse wrote:
> >> > Bonita Montero <Bonita....@gmail.com> writes:
> >> >
> >> > > Am 09.01.2023 um 12:03 schrieb Alf P. Steinbach:
> >> > >
> >> > >> When n is large and is near or equal to the number of possible
> >> > >> values, this loop becomes inefficient: for the last number you can
> >> > >> expect on average n iterations to find that number, because each call
> >> > >> of uid has a 1/n chance of finding it.
> >> > >
> >> > > I know that the loop becomes inefficient then, but tell me a better
> >> > > alternative algorithm.
> >> > An alternative that works well in those cases (and in some others) has
> >> > already been described where each candidate is chosen with the
> >> > appropriate probability. I originally set it out as an exercises since
> >> > I thought the OP was doing homework, but the gist of it was explained.
> >> > > You'd have a list of eligible numbers and
> >> > > randomly chose one of them. That would also take a lot of time to
> >> > > remove the number from the list.
> >> > No need:
> >> >
> >> > void choose(int choose_n, int from_m, int *output)
> >> > {
> >> > for (int i = 0, j = 0; j < choose_n; i++)
> >> > if (true_with_probability(choose_n - j, from_m - i))
> >> > output[j++] = i + 1;
> >> > }
> >> >
> >> > Obviously using one would not use this to choose 3 numbers from a set of
> >> > millions!
> >> >
> >> We're choosing M values from N.
> >> If we choose a random member, i, then we have two sets, 0 to i-1, and i+1 to N-1,
> >> and M-1 values left to choose.
> >> So basically we would expect a binomial distribution, with each remaining value
> >> having an (i-1)/(N-1) chance of ending up in the first set. We then recurse.
> >> However the whole point of the problem is that the distribution is discrete, and this
> >> isn't quite correct, because we could end up with more values to choose than
> >> members of the set. This would happen very rarely if N is large in relation to M,
> >> but it could happen.
> >> I'm not quite sure how to correct for this.
> >>
> > Ah. It's the hypergeometric distribution. Very messy.
> What quantity are you referring to? There may be something that has a
> messy distribution in all of this but (a) I don't know what quantity you
> are talking about and (b) I don't think it matters.
>
The alorithm is we choose M values from a set of N.
So choose a single value, call it i, using a standard uniform random number.
Now we've got M-1 values to choose, from two sets, 0 to i-1, and i+1 to N-1.
So if we take another rnadom number, we can work out how many values
we need from the first set, and thus how many values from the second set,
and we recurse.
But what is the distribution of those values? It's close to binomial. But it's
binomial without repalcement. Which is the hypergeomtric distribution.

However if we can draw one number from the hypergeomtric distribution,
in constant time, then the algorithm is O(M).

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On Tuesday, 10 January 2023 at 03:08:40 UTC, Ben Bacarisse wrote:
>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>
>> > On Tuesday, 10 January 2023 at 02:28:48 UTC, Malcolm McLean wrote:
>> >> On Monday, 9 January 2023 at 23:22:24 UTC, Ben Bacarisse wrote:
>> >> > Bonita Montero <Bonita....@gmail.com> writes:
>> >> >
>> >> > > Am 09.01.2023 um 12:03 schrieb Alf P. Steinbach:
>> >> > >
>> >> > >> When n is large and is near or equal to the number of possible
>> >> > >> values, this loop becomes inefficient: for the last number you can
>> >> > >> expect on average n iterations to find that number, because each call
>> >> > >> of uid has a 1/n chance of finding it.
>> >> > >
>> >> > > I know that the loop becomes inefficient then, but tell me a better
>> >> > > alternative algorithm.
>> >> > An alternative that works well in those cases (and in some others) has
>> >> > already been described where each candidate is chosen with the
>> >> > appropriate probability. I originally set it out as an exercises since
>> >> > I thought the OP was doing homework, but the gist of it was explained.
>> >> > > You'd have a list of eligible numbers and
>> >> > > randomly chose one of them. That would also take a lot of time to
>> >> > > remove the number from the list.
>> >> > No need:
>> >> >
>> >> > void choose(int choose_n, int from_m, int *output)
>> >> > {
>> >> > for (int i = 0, j = 0; j < choose_n; i++)
>> >> > if (true_with_probability(choose_n - j, from_m - i))
>> >> > output[j++] = i + 1;
>> >> > }
>> >> >
>> >> > Obviously using one would not use this to choose 3 numbers from a set of
>> >> > millions!
>> >> >
>> >> We're choosing M values from N.
>> >> If we choose a random member, i, then we have two sets, 0 to i-1, and i+1 to N-1,
>> >> and M-1 values left to choose.
>> >> So basically we would expect a binomial distribution, with each remaining value
>> >> having an (i-1)/(N-1) chance of ending up in the first set. We then recurse.
>> >> However the whole point of the problem is that the distribution is discrete, and this
>> >> isn't quite correct, because we could end up with more values to choose than
>> >> members of the set. This would happen very rarely if N is large in relation to M,
>> >> but it could happen.
>> >> I'm not quite sure how to correct for this.
>> >>
>> > Ah. It's the hypergeometric distribution. Very messy.
>> What quantity are you referring to? There may be something that has a
>> messy distribution in all of this but (a) I don't know what quantity you
>> are talking about and (b) I don't think it matters.
>>
> The alorithm is we choose M values from a set of N.

What algorithm? You posted in direct reply to what I posted. Are you
commenting on that code or just making some tangential remarks? If it's
the latter, a reply to the head post would have been more logical.

> So choose a single value, call it i, using a standard uniform random
> number.

OK, so you are not talking about the algorithm I posted, right?

Ah. I've seen a post in comp.lang.c++ with code and, yes, you are not
commenting on what I wrote.

--
Ben.

On Tuesday, 10 January 2023 at 17:30:37 UTC, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>
> > On Tuesday, 10 January 2023 at 03:08:40 UTC, Ben Bacarisse wrote:
> >> Malcolm McLean <malcolm.ar...@gmail.com> writes:
> >>
> >> > On Tuesday, 10 January 2023 at 02:28:48 UTC, Malcolm McLean wrote:
> >> >> On Monday, 9 January 2023 at 23:22:24 UTC, Ben Bacarisse wrote:
> >> >> > Bonita Montero <Bonita....@gmail.com> writes:
> >> >> >
> >> >> > > Am 09.01.2023 um 12:03 schrieb Alf P. Steinbach:
> >> >> > >
> >> >> > >> When n is large and is near or equal to the number of possible
> >> >> > >> values, this loop becomes inefficient: for the last number you can
> >> >> > >> expect on average n iterations to find that number, because each call
> >> >> > >> of uid has a 1/n chance of finding it.
> >> >> > >
> >> >> > > I know that the loop becomes inefficient then, but tell me a better
> >> >> > > alternative algorithm.
> >> >> > An alternative that works well in those cases (and in some others) has
> >> >> > already been described where each candidate is chosen with the
> >> >> > appropriate probability. I originally set it out as an exercises since
> >> >> > I thought the OP was doing homework, but the gist of it was explained.
> >> >> > > You'd have a list of eligible numbers and
> >> >> > > randomly chose one of them. That would also take a lot of time to
> >> >> > > remove the number from the list.
> >> >> > No need:
> >> >> >
> >> >> > void choose(int choose_n, int from_m, int *output)
> >> >> > {
> >> >> > for (int i = 0, j = 0; j < choose_n; i++)
> >> >> > if (true_with_probability(choose_n - j, from_m - i))
> >> >> > output[j++] = i + 1;
> >> >> > }
> >> >> >
> >> >> > Obviously using one would not use this to choose 3 numbers from a set of
> >> >> > millions!
> >> >> >
> >> >> We're choosing M values from N.
> >> >> If we choose a random member, i, then we have two sets, 0 to i-1, and i+1 to N-1,
> >> >> and M-1 values left to choose.
> >> >> So basically we would expect a binomial distribution, with each remaining value
> >> >> having an (i-1)/(N-1) chance of ending up in the first set. We then recurse.
> >> >> However the whole point of the problem is that the distribution is discrete, and this
> >> >> isn't quite correct, because we could end up with more values to choose than
> >> >> members of the set. This would happen very rarely if N is large in relation to M,
> >> >> but it could happen.
> >> >> I'm not quite sure how to correct for this.
> >> >>
> >> > Ah. It's the hypergeometric distribution. Very messy.
> >> What quantity are you referring to? There may be something that has a
> >> messy distribution in all of this but (a) I don't know what quantity you
> >> are talking about and (b) I don't think it matters.
> >>
> > The alorithm is we choose M values from a set of N.
> What algorithm? You posted in direct reply to what I posted. Are you
> commenting on that code or just making some tangential remarks? If it's
> the latter, a reply to the head post would have been more logical.
> > So choose a single value, call it i, using a standard uniform random
> > number.
> OK, so you are not talking about the algorithm I posted, right?
>
> Ah. I've seen a post in comp.lang.c++ with code and, yes, you are not
> commenting on what I wrote.
>
You said "We would not use this algorithm to choose 3 numbers froma set of millions".
I was responding to that by providing an algorithm which does work well with such
a pair of sets. Sorry if that wasn't clear.

Am 09.01.2023 um 17:42 schrieb Bonita Montero:
> Am 09.01.2023 um 12:03 schrieb Alf P. Steinbach:
>
>> When n is large and is near or equal to the number of possible values,
>> this loop becomes inefficient: for the last number you can expect on
>> average n iterations to find that number, because each call of uid has
>> a 1/n chance of finding it.
>
> I know that the loop becomes inefficient then, but tell me a better
> alternative algorithm. You'd have a list of eligible numbers and
> randomly chose one of them. That would also take a lot of time to
> remove the number from the list.

Now I make a list of eligible numbers, randomly chode one of them
and remove the item from the list:

#include <iostream>
#include <charconv>
#include <random>
#include <concepts>
#include <vector>

using namespace std;

int main( int argc, char **argv )
{ try
{
if( argc < 4 )
return
cout << argv[0] << " n from to" << endl,
EXIT_FAILURE;
auto parse = []( char const *str, char const *err )
{
size_t value;
if( from_chars_result fcr = from_chars( str, str + strlen( str ),
value ); (bool)fcr.ec || *fcr.ptr )
throw invalid_argument( err );
return value;
};
size_t n = parse( argv[1], "wrong number of values" );
if( !n )
return EXIT_SUCCESS;
size_t
from = parse( argv[2], "wrong from-value" ),
to = parse( argv[3], "wrong to-value" );
if( from > to )
swap( from, to );
if( n - 1 > to - from )
return
cout << "n is too small" << endl,
EXIT_FAILURE;
vector<size_t> free;
free.resize( to - from + 1 );
for( size_t i = from; size_t &v : free )
v = i++;
mt19937_64 mt;
size_t above = to;
while( free.size() )
{
auto pick = free.begin() + (uniform_int_distribution<size_t>( 0,
free.size() - 1 ))( mt );
//cout << *pick << endl;
free.erase( pick );
}
}
catch( exception const &exc )
{
return
cout << exc.what() << endl,
EXIT_FAILURE;
}
}

But that's _much_ slower.

On Friday, 13 January 2023 at 07:26:24 UTC, Bonita Montero wrote:
> Am 09.01.2023 um 17:42 schrieb Bonita Montero:
> > Am 09.01.2023 um 12:03 schrieb Alf P. Steinbach:
> >
> >> When n is large and is near or equal to the number of possible values,
> >> this loop becomes inefficient: for the last number you can expect on
> >> average n iterations to find that number, because each call of uid has
> >> a 1/n chance of finding it.
> >
> > I know that the loop becomes inefficient then, but tell me a better
> > alternative algorithm. You'd have a list of eligible numbers and
> > randomly chose one of them. That would also take a lot of time to
> > remove the number from the list.
> Now I make a list of eligible numbers, randomly chode one of them
> and remove the item from the list:
>
> #include <iostream>
> #include <charconv>
> #include <random>
> #include <concepts>
> #include <vector>
> using namespace std;
>
> int main( int argc, char **argv )
> {
> try
> {
> if( argc < 4 )
> return
> cout << argv[0] << " n from to" << endl,
> EXIT_FAILURE;
> auto parse = []( char const *str, char const *err )
> {
> size_t value;
> if( from_chars_result fcr = from_chars( str, str + strlen( str ),
> value ); (bool)fcr.ec || *fcr.ptr )
> throw invalid_argument( err );
> return value;
> };
> size_t n = parse( argv[1], "wrong number of values" );
> if( !n )
> return EXIT_SUCCESS;
> size_t
> from = parse( argv[2], "wrong from-value" ),
> to = parse( argv[3], "wrong to-value" );
> if( from > to )
> swap( from, to );
> if( n - 1 > to - from )
> return
> cout << "n is too small" << endl,
> EXIT_FAILURE;
> vector<size_t> free;
> free.resize( to - from + 1 );
> for( size_t i = from; size_t &v : free )
> v = i++;
> mt19937_64 mt;
> size_t above = to;
> while( free.size() )
> {
> auto pick = free.begin() + (uniform_int_distribution<size_t>( 0,
> free.size() - 1 ))( mt );
> //cout << *pick << endl;
> free.erase( pick );
> }
> }
> catch( exception const &exc )
> {
> return
> cout << exc.what() << endl,
> EXIT_FAILURE;
> }
> }
> But that's _much_ slower.
>
Yes. If you construct a list of "free" choice, then the algorithm is at least O(N), where
N is the number of items to choose from. If you use a vector and delete, then it's
O(NM), where M is the number of choices. However you can change this by using
a container which allows for O(log N) deletion.

Run time is inherently at least O(M), where M is the number of choices. The question is
how far you can get down the other factors. And you need to avoid catastrophic behaviour
when M gets close to N. The other behaviour to avoid is an N term in the runtime, if N can
be very large.

In article <tpr12i$1i7r6$1@dont-email.me>,
some lunatic <Bonita.Montero@gmail.com> wrote:
....
>Now I make a list of eligible numbers, randomly chode one of them
>and remove the item from the list:
>
>#include <iostream>
>#include <charconv>
>#include <random>
>#include <concepts>
>#include <vector>

You still just don't seem to get this whole topicality thing, do ya?

--
Reading any post by Fred Hodgin, you're always faced with the choice of:
lunatic, moron, or troll.

I always try to be generous and give benefit of the doubt, by assuming troll.

Am 13.01.2023 um 13:21 schrieb Kenny McCormack:
> In article <tpr12i$1i7r6$1@dont-email.me>,
> some lunatic <Bonita.Montero@gmail.com> wrote:
> ...
>> Now I make a list of eligible numbers, randomly chode one of them
>> and remove the item from the list:
>>
>> #include <iostream>
>> #include <charconv>
>> #include <random>
>> #include <concepts>
>> #include <vector>
>
> You still just don't seem to get this whole topicality thing, do ya?

My code is beyond that topic. You may elect only a small number
of values like in the original code, but you might also chose
million of numbers.

In article <tprl89$1k839$1@dont-email.me>,
some lunatic <Bonita.Montero@gmail.com> wrote:
>Am 13.01.2023 um 13:21 schrieb Kenny McCormack:
>> In article <tpr12i$1i7r6$1@dont-email.me>,
>> some lunatic <Bonita.Montero@gmail.com> wrote:
>> ...
>>> Now I make a list of eligible numbers, randomly chode one of them
>>> and remove the item from the list:
>>>
>>> #include <iostream>
>>> #include <charconv>
>>> #include <random>
>>> #include <concepts>
>>> #include <vector>
>>
>> You still just don't seem to get this whole topicality thing, do ya?
>
>My code is beyond that topic. You may elect only a small number
>of values like in the original code, but you might also chose
>million of numbers.

Whoooooosh!!!

--
Many people in the American South think that DJT is, and will be remembered
as, one of the best presidents in US history. They are absolutely correct.

He is currently at number 46 on the list. High praise, indeed!

Am 13.01.2023 um 14:55 schrieb Kenny McCormack:
> In article <tprl89$1k839$1@dont-email.me>,
> some lunatic <Bonita.Montero@gmail.com> wrote:
>> Am 13.01.2023 um 13:21 schrieb Kenny McCormack:
>>> In article <tpr12i$1i7r6$1@dont-email.me>,
>>> some lunatic <Bonita.Montero@gmail.com> wrote:
>>> ...
>>>> Now I make a list of eligible numbers, randomly chode one of them
>>>> and remove the item from the list:
>>>>
>>>> #include <iostream>
>>>> #include <charconv>
>>>> #include <random>
>>>> #include <concepts>
>>>> #include <vector>
>>>
>>> You still just don't seem to get this whole topicality thing, do ya?
>>
>> My code is beyond that topic. You may elect only a small number
>> of values like in the original code, but you might also chose
>> million of numbers.
>
> Whoooooosh!!!

It's not the absolute number of values which can be chosen
but the flexibility or finding the most efficient way to
have this flexibility.

In article <tpro7o$1ki63$1@dont-email.me>,
some lunatic <Bonita.Montero@gmail.com> wrote:
>Am 13.01.2023 um 14:55 schrieb Kenny McCormack:
>> In article <tprl89$1k839$1@dont-email.me>,
>> some lunatic <Bonita.Montero@gmail.com> wrote:
>>> Am 13.01.2023 um 13:21 schrieb Kenny McCormack:
>>>> In article <tpr12i$1i7r6$1@dont-email.me>,
>>>> some lunatic <Bonita.Montero@gmail.com> wrote:
>>>> ...
>>>>> Now I make a list of eligible numbers, randomly chode one of them
>>>>> and remove the item from the list:
>>>>>
>>>>> #include <iostream>
>>>>> #include <charconv>
>>>>> #include <random>
>>>>> #include <concepts>
>>>>> #include <vector>
>>>>
>>>> You still just don't seem to get this whole topicality thing, do ya?
>>>
>>> My code is beyond that topic. You may elect only a small number
>>> of values like in the original code, but you might also chose
>>> million of numbers.
>>
>> Whoooooosh!!!
>
>It's not the absolute number of values which can be chosen
>but the flexibility or finding the most efficient way to
>have this flexibility.

Due anziani che convivono da una vita:
Lei: "Caro, ormai ci potremmo anche sposare...".
Lui: "Ma cara, alla nostra eta', chi ci prenderebbe?".

--
"Women should not be enlightened or educated in any way. They should be
segregated because they are the cause of unholy erections in holy men.

-- Saint Augustine (354-430) --

Albert <invalid@gmail.com> wrote:
> Is this the best way to generate unique random numbers in a set of 6
> numbers? <snip>

I think what you're looking for (not sure whether or not it's already
been mentioned in this long thread) is a "partial permutation",
swapping used numbers with unused ones, but we don't need to save the
used ones. Here's my general solution, and cc -DTESTDRIVE for the
main() test driver...

/* ---
* uniqrand.c
* Generate nuniq random numbers in the range lorand...hirand
* ---
* (optional) command-line arguments:
* ./uniqrand nuniq lorand hirand seedval
* 100 1 999 864297531 <-- default test values
* ------------------------------------------------------------------------ */

/* --- standard headers --- */
#include <stdio.h>
#include <stdlib.h>
#include <sys/param.h> /* for MIN(i,j) macro */

/* --- standard headers --- */
#include <stdio.h>
#include <stdlib.h>
#include <sys/param.h> /* for MIN(i,j) macro */

/* --- entry point --- */
int *uniqrand ( int nuniq, int lorand, int hirand ) {
/* --- allocations and declarations --- */
int iuniq = 0; /* index 0...nuniq-1 */
int range = 1+abs(hirand-lorand); /* random number range */
int *randvals = NULL, /* nuniq ints returned to caller */
*rangevals = NULL; /* all numbers lorand...hirand */
/* --- initialization --- */
if ( nuniq<1 || nuniq>range ) goto end_of_job; /* input error */
randvals = (int *)malloc((nuniq+99)*sizeof(int)); /* caller free()'s */
rangevals = (int *)malloc((range+99)*sizeof(int)); /* we free() work area */
if ( randvals==NULL || rangevals==NULL ) goto end_of_job; /* malloc error */
rangevals[0] = MIN(lorand,hirand); /* in case hirand<lorand */
for ( iuniq=1; iuniq<range; iuniq++ ) /* all numbers lorand...hirand... */
rangevals[iuniq] = rangevals[0] + iuniq; /* ...or vice versa */
/* --- generate nuniq unique random numbers from lorand to hirand --- */
for ( iuniq=0; iuniq<nuniq; iuniq++ ) {
int thisrand = rand()%range; /* random number 0...range-1 */
randvals[iuniq] = rangevals[thisrand]; /* unique random lorand...hirand */
rangevals[thisrand] = rangevals[--range]; } /* replace used number */
/* --- end-of-job --- */
end_of_job:
if ( rangevals != NULL ) free((void *)rangevals);
return ( randvals );
} /* --- end-of-function uniqrand() --- */

#if defined(TESTDRIVE)
/* --- entry point --- */
int main ( int argc, char *argv[] ) {
/* --- command-line arguments --- */
int nuniq = ( argc>1? atoi(argv[1]) : 100 ),
lorand = ( argc>2? atoi(argv[2]) : 1 ),
hirand = ( argc>3? atoi(argv[3]) : 999 ),
seedval = ( argc>4? atoi(argv[4]) : 164897532 );
/* --- allocations and declarations --- */
int *uniqrand(), *randvals=NULL; /* randvals from uniqrand() */
int iuniq = 0; /* randvals[] index */
/* --- initialization --- */
if ( seedval > 0 ) srand(seedval); /* initialize rand() */
/* --- call uniqrand() and display results --- */
if ( (randvals=uniqrand(nuniq,lorand,hirand)) == NULL ) goto end_of_job;
for ( iuniq=0; iuniq<nuniq; iuniq++ )
printf("%7d%s",randvals[iuniq],
(iuniq==nuniq-1?"\n":((iuniq+1)%8==0?",\n":",")) );
/* --- end-of-job --- */
end_of_job:
if ( randvals != NULL ) free((void *)randvals);
exit ( 0 );
} /* --- end-of-function main() --- */
#endif
/* --- end-of-file uniqrand.c --- */

John Forkosh ( mailto: j@f.com where j=john and f=forkosh )

Now it's perfect:

#include <iostream>
#include <unordered_set>
#include <charconv>
#include <random>
#include <concepts>

using namespace std;

int main( int argc, char** argv )
{ try
{
if( argc < 4 )
return
cout << argv[0] << " n from to" << endl,
EXIT_FAILURE;
auto parse = []( char const *str, char const *err )
{
size_t value;
if( from_chars_result fcr = from_chars( str, str + strlen( str ),
value ); (bool)fcr.ec || *fcr.ptr )
throw invalid_argument( err );
return value;
};
size_t n = parse( argv[1], "wrong number of values" );
if( !n )
return EXIT_SUCCESS;
size_t
from = parse( argv[2], "wrong from-value" ),
to = parse( argv[3], "wrong to-value" );
if( from > to )
swap(from, to);
if( n - 1 > to - from )
return
cout << "n is too small" << endl,
EXIT_FAILURE;
unordered_set<size_t> values;
mt19937_64 mt;
uniform_int_distribution<size_t> uid( from, to );
if( to - from != (size_t)-1 && to - from + 1 < n / 2 )
{
values.reserve( n );
while( values.size() < n )
{
size_t value;
do
value = uid( mt );
while( values.contains( value ) );
values.emplace( value );
}
}
else
{
if( to - from == (size_t)-1 )
throw bad_alloc();
values.reserve( to - from + 1 );
size_t i = from - 1;
do
values.emplace( ++i );
while( i != to );
while( values.size() > n )
for( ; ; )
{
auto itRemove = values.find( uid( mt ) );
if( itRemove == values.end() )
continue;
values.erase( itRemove );
break;
}
}
for( size_t value : values )
cout << value << endl;
}
catch( exception const &exc )
{
return
cout << exc.what() << endl,
EXIT_FAILURE;
}
}

If less than half of the range of numbers is selected (n < (to - from
+ 1) / 2) the unordered map is filled up to n elements and if an element
is found that's already there another value is chosen. If more than half
of the range is selected (n >= (to - from + 1) / 2) the set is filled up
to contain the whole range and the elements are incrementally removed at
a random value.

On 15/01/2023 15:06, Bonita Montero wrote:
> Now it's perfect:

You said that last time too:

On 08/01/2023 05:01, Bonita Montero wrote:
> Now it's perfect:
>

I guess it's more perfect?

Am 15.01.2023 um 17:27 schrieb Bart:
> On 15/01/2023 15:06, Bonita Montero wrote:
>> Now it's perfect:
>
> You said that last time too:
>
> On 08/01/2023 05:01, Bonita Montero wrote:
> > Now it's perfect:
> >
>
>
> I guess it's more perfect?

The code I've shown yet is also perfect in terms of performance,
but not just functionally.

In article <tq14n7$2cgbf$1@dont-email.me>,
Bonita Montero <Bonita.Montero@gmail.com> wrote:
>Now it's perfect:

I just need 11,780 votes. Give me a break here.

--
If Jeb is Charlie Brown kicking a football-pulled-away, Mitt is a '50s
housewife with a black eye who insists to her friends the roast wasn't
dry.