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

Groups > comp.lang.c > #168644 > unrolled thread

Compute Unique Numbers in a Set

Back to article view | Back to comp.lang.c

Contents

  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 2 of 5 — ← Prev page 1 [2] 3 4 5  Next page →

#168672

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

This seems highly inefficient to me, IIUC.

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


Regards,
Mike.

[toc] | [prev] | [next] | [standalone]

#168676

Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:

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

Highly?  Surely that depends on the costs.  PRNGs are often extremely
cheap, and there's something to be said for an algorithm that is three
lines with no extra storage at all!

Anyway, I think the OP will benefit from seeing a wide range of methods.
I think this is a learning exercise.  I doubt they have a real
application with tight resource bounds, and if they do they didn't tell
us.

> We have a range of 60 numbers, and we only want 6 of them.  With your
> method, the expected number of random numbers we have to generate is,
> um, I think (60 - 54/7) ?  That's around 52.?

Yes.  If random numbers are the key cost, then I'd use something else.
I just posted another algorithm that uses the minimum number of calls.

> Everyone elses methods only have 6 random number generations, plus
> what seems to me a small overhead to avoid selecting a duplicate.  52
> vs 6+smalloverhead ???

There's no entirely optimal solution for the general case.  For example,
if you worry about wasted random number calls, then you probably don't
want to use a stochastic method when the number of items to be chosen is
close to the number range.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#168678

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> 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) [...]

If you look in the original posting, I think you will see that
the set of values is between 1 and 59 inclusive, that is, only
59 values.  (That may have been a mistake by OP, but I offer
no opinion on that question.)

[toc] | [prev] | [next] | [standalone]

#168663

On 26/12/2022 23:45, Albert wrote:
> Is this the best way to generate unique random numbers in a set of 6
> numbers?
>
>
>

I checked your code by creating a Windows Forms application 
<https://i.imgur.com/STme6ya.png> and it works so the numbers are 
"Unique". By unique I mean the numbers don't repeat in the same line.

There are 15 comparisons:

Num1 -> 0
Num2 -> 1
Num3 -> 2
Num4 -> 3
Num5 -> 4
Num6 -> 5

I guess you have to compare each number when generated otherwise you
get repeats because of randomness. There is no way to avoid this as far 
as I can see.

Whether it is the best way to do is for you to decide but for this small 
program it doesn't matter, or does it? Is this asked on coding 
competitions? Please provide a link if you have it.

I can post a video to show how the numbers change when clicking on the 
Generate button as shown in the picture.

[toc] | [prev] | [next] | [standalone]

#168673

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

"unique random numbers in a set of 6 numbers" is strange formulation
of the problem.  In such a small set you get at most 6 numbers
without repeating.  If you want exactly 6, this is (random) permutation
of original numbers.  There is standard, resonably efficient
algoritm for generating random permutations of N elements.  Assuming
numbering starting from 1, as step 1, swap number at first position N
with number at random postion (if random position happens to be N this
is a no-op).  Then recursively do generate random permutation of positions
1 to N - 1.  This is easy to implement as a loop, but presentation
is simpler in recursive way.

If you need less numbers than N, then you can use firs k < N positions
of random permutation.  Different methods make sense only if size
of your set (that in N) is much larger than number of random numbers
that you need (that is k).  For N = 6 there is no reason to do
anything more complicated than generating random permutation.

-- 
                              Waldek Hebisch

[toc] | [prev] | [next] | [standalone]

#168674

On 12/27/22 8:32 PM, antispam@math.uni.wroc.pl wrote:
> Albert <invalid@gmail.com> wrote:
>> Is this the best way to generate unique random numbers in a set of 6
>> numbers?
> 
> "unique random numbers in a set of 6 numbers" is strange formulation
> of the problem.  In such a small set you get at most 6 numbers

No, it is a classical problem, the physical model is drawing from a 
sack/bag without replacement.

> without repeating.  If you want exactly 6, this is (random) permutation
> of original numbers.  There is standard, resonably efficient
> algoritm for generating random permutations of N elements.  Assuming
> numbering starting from 1, as step 1, swap number at first position N
> with number at random postion (if random position happens to be N this
> is a no-op).  Then recursively do generate random permutation of positions
> 1 to N - 1.  This is easy to implement as a loop, but presentation
> is simpler in recursive way.
> 
> If you need less numbers than N, then you can use firs k < N positions
> of random permutation.  Different methods make sense only if size
> of your set (that in N) is much larger than number of random numbers
> that you need (that is k).  For N = 6 there is no reason to do
> anything more complicated than generating random permutation.
> 

The issue with the permutation methods is you need to set up the "bag" 
of ALL POSSIBLE numbers.  In this case, 60 isn't THAT big, so not so 
much of an issue. If the "bag" (the universe being selected from) gets 
much larger, creating a copy of that set to do the permutation set 
becomes a lot of extra work that isn't needed.

If you are drawing a signifcant fraction of the set, then it becomes 
more reasonable.

Note, in this case N = *60* and *k* = 6 (we are drawing 6 numbers from 
the set of 60, not out of just 6 numbers. Yes, the OP was a bit sloppy 
with his words, but from the code they gave, their intent was clear.

Also, I find the loop presentation fairly clear, and the converting to 
recursion tends to make the system much harder to "short cut" to the 
partial version where you only need k out of N choices.

[toc] | [prev] | [next] | [standalone]

#168679

Richard Damon <Richard@Damon-Family.org> writes:

[.. choosing a small number of values out of N possible values ..]

> Note, in this case N = *60* and *k* = 6 (we are drawing 6 numbers
> from the set of 60, not out of just 6 numbers.  Yes, the OP was a
> bit sloppy with his words, but from the code they gave, their intent
> was clear.

The code given by OP produced values from 1 to 59 inclusive, yes?
That's only 59 values.

[toc] | [prev] | [next] | [standalone]

#168681

On 12/27/22 10:48 PM, Tim Rentsch wrote:
> Richard Damon <Richard@Damon-Family.org> writes:
> 
> [.. choosing a small number of values out of N possible values ..]
> 
>> Note, in this case N = *60* and *k* = 6 (we are drawing 6 numbers
>> from the set of 60, not out of just 6 numbers.  Yes, the OP was a
>> bit sloppy with his words, but from the code they gave, their intent
>> was clear.
> 
> The code given by OP produced values from 1 to 59 inclusive, yes?
> That's only 59 values.

Yes, I mis-remembered his range. Perhaps because a random number 1-60 
seems to have more application that 1-59. I was thinking he got 0-59 
from the % operator, not 0-58.

[toc] | [prev] | [next] | [standalone]

#168688

Richard Damon <Richard@damon-family.org> wrote:
> On 12/27/22 8:32 PM, antispam@math.uni.wroc.pl wrote:
> > Albert <invalid@gmail.com> wrote:
> >> Is this the best way to generate unique random numbers in a set of 6
> >> numbers?
> > 
> > "unique random numbers in a set of 6 numbers" is strange formulation
> > of the problem.  In such a small set you get at most 6 numbers
> 
> No, it is a classical problem, the physical model is drawing from a 
> sack/bag without replacement.

Problem of "drawing without replacement" is classic.  Formulating
this as "unique random numbers in a set of 6 numbers" is strange.

> > without repeating.  If you want exactly 6, this is (random) permutation
> > of original numbers.  There is standard, resonably efficient
> > algoritm for generating random permutations of N elements.  Assuming
> > numbering starting from 1, as step 1, swap number at first position N
> > with number at random postion (if random position happens to be N this
> > is a no-op).  Then recursively do generate random permutation of positions
> > 1 to N - 1.  This is easy to implement as a loop, but presentation
> > is simpler in recursive way.
> > 
> > If you need less numbers than N, then you can use firs k < N positions
> > of random permutation.  Different methods make sense only if size
> > of your set (that in N) is much larger than number of random numbers
> > that you need (that is k).  For N = 6 there is no reason to do
> > anything more complicated than generating random permutation.
> > 
> 
> The issue with the permutation methods is you need to set up the "bag" 
> of ALL POSSIBLE numbers.  In this case, 60 isn't THAT big, so not so 
> much of an issue. If the "bag" (the universe being selected from) gets 
> much larger, creating a copy of that set to do the permutation set 
> becomes a lot of extra work that isn't needed.

Yes, this is different wording of what I wrote.

> If you are drawing a signifcant fraction of the set, then it becomes 
> more reasonable.
> 
> Note, in this case N = *60* and *k* = 6 (we are drawing 6 numbers from 
> the set of 60, not out of just 6 numbers. Yes, the OP was a bit sloppy 
> with his words, but from the code they gave, their intent was clear.

I admit that code looked so crappy that I did not want to analyse
it.  And to say the truth, my approch is: first say clearly what
should be done, then code this.  Without clear statement of intent
one never know if some irregularity is a bug or a feature.

-- 
                              Waldek Hebisch

[toc] | [prev] | [next] | [standalone]

#168682

Il 27/12/2022 00:45, Albert ha scritto:
> 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;
> }

using a lookup table?

void generateNumbers()
{
     char num_flag[61];
     int  val[6];

     memset(num_flag, '\0', sizeof(num_flag));

     for(int i = 0; i < 6; i++)
     {
         while(num_flag[val[i] = rand() % 59 + 1]);
         num_flag[val[i]] = 1;
     }

     printf("\n");
     for(int i = 0; i < 6; i++)
         printf("%d ", val[i]);
     printf("\n");
}

[toc] | [prev] | [next] | [standalone]

#168700

On Mon, 26 Dec 2022 23:45:04 +0000, Albert <invalid@gmail.com> wrote:

>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;
>}


int  array[6];

int*f(void)
{int i,j,c,t;
 for(i=0;i<6;++i) array[i]=0;
 srand((unsigned int)time(0));
 for(c=0;c<10;++c)
    {i=rand()%6; j=rand()%6;
     if(i!=j){t=array[i];array[i]=array[j];array[j]=t;}
    }
 return array;
}

int main(void)
{int i, *a ;
 a=f(); 
 for(i=0;i<6;++i) printf("%d ", a[i]);
 printf("\n");
 return 0;
}

[toc] | [prev] | [next] | [standalone]

#168702

On Sun, 01 Jan 2023 21:06:50 +0100, Rosario19 <Ros@invalid.invalid>
wrote:

On Mon, 26 Dec 2022 23:45:04 +0000, Albert <invalid@gmail.com> wrote:

>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;
>}


int  array[59];

int*f(void)
{int i,j,c,t;
 for(i=0;i<59;++i) array[i]=i+1;
 srand((unsigned int)time(0));
 for(c=0;c<100;++c)
    {i=rand()%59; j=rand()%59;
     if(i!=j){t=array[i];array[i]=array[j];array[j]=t;}
    }
 return array;
}

int main(void)
{int i, *a ;
 a=f(); 
 for(i=0;i<6;++i) printf("%d ", a[i]);
 printf("\n");
 return 0;
}

[toc] | [prev] | [next] | [standalone]

#168701

In article <todbqe$16sg$1@gioia.aioe.org>, Albert  <invalid@gmail.com> wrote:
>Is this the best way to generate unique random numbers in a set of 6 
>numbers?
>
>
><******************************************************>

Here's my contribution to this thread.

Note that this is both gcc- and Linux- specific, as well as being
hard-coded to OP's problem specification.  Note also that I took the
liberty of assuming that OP actually, really, did want random numbers
between 0 and 59; this would be suitable if, say, OP was looking for a
random number of minutes or seconds (and we could be talking either about
time intervals or about locations/distances expressed in terms of latitude
and/or longitude).

--- Cut Here ---
#include <stdio.h>
#include <stdint.h>

int main(void)
{
    uint64_t num = 0, j = 1;
    FILE *fp = fopen("/dev/urandom","r");

    while (__builtin_popcount(num) < 6)
	num |= 1 << (fgetc(fp) % 60);

    for (int i=0; i<60; i++, j *= 2)
	if (num & j)
	    printf("i = %d, j = %ld\n",i,j);
    return 0;
}
--- Cut Here ---

The values printed out of the variable "i" are your random numbers.

-- 
People who say they'll vote for someone else because Obama couldn't fix
*all* of Bush's messes are like people complaining that he couldn't cure
cancer, so they'll go and vote for (more) cancer.

[toc] | [prev] | [next] | [standalone]

#168703

Il 02/01/2023 00:19, Kenny McCormack ha scritto:
> In article <todbqe$16sg$1@gioia.aioe.org>, Albert  <invalid@gmail.com> wrote:
>> Is this the best way to generate unique random numbers in a set of 6
>> numbers?
>>
>>
>> <******************************************************>
> 
> Here's my contribution to this thread.
> 
> Note that this is both gcc- and Linux- specific, as well as being
> hard-coded to OP's problem specification.  Note also that I took the
> liberty of assuming that OP actually, really, did want random numbers
> between 0 and 59; this would be suitable if, say, OP was looking for a
> random number of minutes or seconds (and we could be talking either about
> time intervals or about locations/distances expressed in terms of latitude
> and/or longitude).
> 
> --- Cut Here ---
> #include <stdio.h>
> #include <stdint.h>
> 
> int main(void)
> {
>      uint64_t num = 0, j = 1;
>      FILE *fp = fopen("/dev/urandom","r");
> 
>      while (__builtin_popcount(num) < 6)
> 	num |= 1 << (fgetc(fp) % 60);
> 
>      for (int i=0; i<60; i++, j *= 2)
> 	if (num & j)
> 	    printf("i = %d, j = %ld\n",i,j);
>      return 0;
> }
> --- Cut Here ---
> 
> The values printed out of the variable "i" are your random numbers.
> 

HI,
I state that I have not worried about the randomization algorithm chosen
by the OP and, so I focused on data storage.
Your storage method is similar to mine because both algorithms use a
lookup table with the difference that mine uses an array of characters
while your use the bits of an uint64_t. However I found a few Issues in
your source code:

The first concerns the use of the "__builtin_popcount" function, this
function does not work with uint64_t but with unsigned int.


#include <stdio.h>
#include <stdint.h>

int main()
{
     uint64_t n = ~0;

     printf ("value: %#lX bits: %d", n, __builtin_popcount(n));

     return 0;
}

output:   value: 0XFFFFFFFFFFFFFFFF bits: 32

This will have as a consequence that you will never get values greater 
than 32.


The second issue concerns that your program will print the values 
archived in numerical order and not in extraction order but perhaps this 
does not affect the OP even if reading his code this seemed important.

[toc] | [prev] | [next] | [standalone]

#168704

Il 02/01/2023 07:28, jak ha scritto:
> Il 02/01/2023 00:19, Kenny McCormack ha scritto:
>> In article <todbqe$16sg$1@gioia.aioe.org>, Albert  <invalid@gmail.com> 
>> wrote:
>>> Is this the best way to generate unique random numbers in a set of 6
>>> numbers?
>>>
>>>
>>> <******************************************************>
>>
>> Here's my contribution to this thread.
>>
>> Note that this is both gcc- and Linux- specific, as well as being
>> hard-coded to OP's problem specification.  Note also that I took the
>> liberty of assuming that OP actually, really, did want random numbers
>> between 0 and 59; this would be suitable if, say, OP was looking for a
>> random number of minutes or seconds (and we could be talking either about
>> time intervals or about locations/distances expressed in terms of 
>> latitude
>> and/or longitude).
>>
>> --- Cut Here ---
>> #include <stdio.h>
>> #include <stdint.h>
>>
>> int main(void)
>> {
>>      uint64_t num = 0, j = 1;
>>      FILE *fp = fopen("/dev/urandom","r");
>>
>>      while (__builtin_popcount(num) < 6)
>>     num |= 1 << (fgetc(fp) % 60);
>>
>>      for (int i=0; i<60; i++, j *= 2)
>>     if (num & j)
>>         printf("i = %d, j = %ld\n",i,j);
>>      return 0;
>> }
>> --- Cut Here ---
>>
>> The values printed out of the variable "i" are your random numbers.
>>
> 
> HI,
> I state that I have not worried about the randomization algorithm chosen
> by the OP and, so I focused on data storage.
> Your storage method is similar to mine because both algorithms use a
> lookup table with the difference that mine uses an array of characters
> while your use the bits of an uint64_t. However I found a few Issues in
> your source code:
> 
> The first concerns the use of the "__builtin_popcount" function, this
> function does not work with uint64_t but with unsigned int.
> 
> 
> #include <stdio.h>
> #include <stdint.h>
> 
> int main()
> {
>      uint64_t n = ~0;
> 
>      printf ("value: %#lX bits: %d", n, __builtin_popcount(n));
> 
>      return 0;
> }
> 
> output:   value: 0XFFFFFFFFFFFFFFFF bits: 32
> 
> This will have as a consequence that you will never get values greater 
> than 32.
> 

I said a wrong thing: you will have numbers greater than 32 but you will 
only know when 6 of them are in range 1-32 so you could print more than 
6 of them.

> 
> The second issue concerns that your program will print the values 
> archived in numerical order and not in extraction order but perhaps this 
> does not affect the OP even if reading his code this seemed important.
> 

[toc] | [prev] | [next] | [standalone]

#168705

jak <nospam@please.ty> writes:

> Il 02/01/2023 00:19, Kenny McCormack ha scritto:
>
>> In article <todbqe$16sg$1@gioia.aioe.org>, Albert wrote:
>>
>>> Is this the best way to generate unique random numbers in a set of
>>> 6 numbers?
>>>
>>>
>>> <******************************************************>
>>
>> Here's my contribution to this thread.
>>
>> Note that this is both gcc- and Linux- specific, as well as being
>> hard-coded to OP's problem specification.  Note also that I took
>> the liberty of assuming that OP actually, really, did want random
>> numbers between 0 and 59;  this would be suitable if, say, OP was
>> looking for a random number of minutes or seconds (and we could be
>> talking either about time intervals or about locations/distances
>> expressed in terms of latitude and/or longitude).
>>
>> --- Cut Here ---
>> #include <stdio.h>
>> #include <stdint.h>
>>
>> int main(void)
>> {
>>      uint64_t num = 0, j = 1;
>>      FILE *fp = fopen("/dev/urandom","r");
>>
>>      while (__builtin_popcount(num) < 6)
>> 	num |= 1 << (fgetc(fp) % 60);
>>
>>      for (int i=0; i<60; i++, j *= 2)
>> 	if (num & j)
>> 	    printf("i = %d, j = %ld\n",i,j);
>>      return 0;
>> }
>> --- Cut Here ---
>>
>> The values printed out of the variable "i" are your random numbers.
>
> HI,

> I state that I have not worried about the randomization algorithm
> chosen by the OP and, so I focused on data storage.  Your storage
> method is similar to mine because both algorithms use a lookup table
> with the difference that mine uses an array of characters while your
> use the bits of an uint64_t.  However I found a few Issues in your
> source code:
>
> The first concerns the use of the "__builtin_popcount" function, this
> function does not work with uint64_t but with unsigned int. [...]
>
> The second issue concerns that your program will print the values
> archived in numerical order and not in extraction order but perhaps
> this does not affect the OP even if reading his code this seemed
> important.

A third problem is that the way the [ 0 .. 59 ] values are
chosen is horribly biased:  some numbers are 25% more likely
than others.

[toc] | [prev] | [next] | [standalone]

#168706

On Monday, 2 January 2023 at 09:54:05 UTC+2, Tim Rentsch wrote:
> jak <nos...@please.ty> writes: 
> 
> > Il 02/01/2023 00:19, Kenny McCormack ha scritto: 
> >
> >> In article <todbqe$16sg$1...@gioia.aioe.org>, Albert wrote: 
> >> 
> >>> Is this the best way to generate unique random numbers in a set of 
> >>> 6 numbers? 
> >>> 
> >>> 
> >>> <******************************************************> 
> >> 
> >> Here's my contribution to this thread. 
> >> 
> >> Note that this is both gcc- and Linux- specific, as well as being 
> >> hard-coded to OP's problem specification. Note also that I took 
> >> the liberty of assuming that OP actually, really, did want random 
> >> numbers between 0 and 59; this would be suitable if, say, OP was 
> >> looking for a random number of minutes or seconds (and we could be 
> >> talking either about time intervals or about locations/distances 
> >> expressed in terms of latitude and/or longitude). 
> >> 
> >> --- Cut Here --- 
> >> #include <stdio.h> 
> >> #include <stdint.h> 
> >> 
> >> int main(void) 
> >> { 
> >> uint64_t num = 0, j = 1; 
> >> FILE *fp = fopen("/dev/urandom","r"); 
> >> 
> >> while (__builtin_popcount(num) < 6) 
> >> num |= 1 << (fgetc(fp) % 60); 
> >> 
> >> for (int i=0; i<60; i++, j *= 2) 
> >> if (num & j) 
> >> printf("i = %d, j = %ld\n",i,j); 
> >> return 0; 
> >> } 
> >> --- Cut Here --- 
> >> 
> >> The values printed out of the variable "i" are your random numbers. 
> > 
> > HI, 
> 
> > I state that I have not worried about the randomization algorithm 
> > chosen by the OP and, so I focused on data storage. Your storage 
> > method is similar to mine because both algorithms use a lookup table 
> > with the difference that mine uses an array of characters while your 
> > use the bits of an uint64_t. However I found a few Issues in your 
> > source code: 
> > 
> > The first concerns the use of the "__builtin_popcount" function, this
> > function does not work with uint64_t but with unsigned int. [...]
> > 
> > The second issue concerns that your program will print the values 
> > archived in numerical order and not in extraction order but perhaps 
> > this does not affect the OP even if reading his code this seemed 
> > important.
> A third problem is that the way the [ 0 .. 59 ] values are 
> chosen is horribly biased: some numbers are 25% more likely 
> than others.

Fourth problem is that 32 bit shift:
num |= 1 << (fgetc(fp) % 60); 
should be:
num |= 1LL << (fgetc(fp) % 60); 

[toc] | [prev] | [next] | [standalone]

#168709

In article <tot4eh$21qv0$1@news.xmission.com>,
Kenny McCormack <gazelle@shell.xmission.com> wrote:
>In article <todbqe$16sg$1@gioia.aioe.org>, Albert  <invalid@gmail.com> wrote:
>>Is this the best way to generate unique random numbers in a set of 6 
>>numbers?
>>
>>
>><******************************************************>
>
>Here's my contribution to this thread.
>
>Note that this is both gcc- and Linux- specific, as well as being
>hard-coded to OP's problem specification.  Note also that I took the
>liberty of assuming that OP actually, really, did want random numbers
>between 0 and 59; this would be suitable if, say, OP was looking for a
>random number of minutes or seconds (and we could be talking either about
>time intervals or about locations/distances expressed in terms of latitude
>and/or longitude).

Here is an updated version that addresses some of the concerns raised by
another poster:

--- Cut Here ---
#include <stdio.h>
#include <stdint.h>

int main(void)
{
    union {
	uint64_t num64;
	struct { unsigned a,b; } num32;
	} num;
    uint64_t j = 1;
    FILE *fp = fopen("/dev/urandom","r");

    num.num64 = 0;
    while (__builtin_popcount(num.num32.a)+__builtin_popcount(num.num32.b) < 6)
	num.num64 |= 1L << (fgetc(fp) % 60);

    for (int i=0; i<60; i++, j *= 2)
	if (num.num64 & j)
	    printf("i = %d, j = %ld\n",i,j);
    return 0;
}
--- Cut Here ---

The values printed out of the variable "i" are your random numbers.

-- 
> No, I haven't, that's why I'm asking questions. If you won't help me,
> why don't you just go find your lost manhood elsewhere.

CLC in a nutshell.

[toc] | [prev] | [next] | [standalone]

#168708

On 26/12/2022 23:45, Albert wrote:
> 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;
> }

Assuming you want generate numbers in the range 1..59, then it seems to 
work, in creating reasonably distributed values (I don't know about a 
smaller range).

The function could do with some work however:

* Extract the rand()%59+1 into its own function

* Make val1..val6 into an array of 6 values (indexed 1..6 if your like, 
just make sure it has 7 elements)

* Rewrite the body as a loop of loops, since there is a lot of 
duplicatation at the moment. Think about how it would look if you wanted 
val1 to val100 instead; it doesn't scale.

* Perhaps let generateNumbers() return an array of numbers, and let the 
caller decide whether to print them or not (which can be done in another 
loop).

[toc] | [prev] | [next] | [standalone]

#168711

On 1/2/23 10:22 AM, Stefan Ram wrote:
> Albert <invalid@gmail.com> writes:
>> Subject: Compute Unique Numbers in a Set
> 
>    In a set, every number is unique.
>

Assuming you are using the right Technical definition of Set.

[toc] | [prev] | [next] | [standalone]

Page 2 of 5 — ← Prev page 1 [2] 3 4 5  Next page →

Back to top | Article view | comp.lang.c

csiph-web