Post Reply 
Random Integers, No Repeats
08-09-2023, 02:30 AM
Post: #1
Random Integers, No Repeats
I cannot remember how to generate random numbers from x to y with no repeats…anybody know how to accomplish this using the RANDINT or randint command?
Find all posts by this user
Quote this message in a reply
08-09-2023, 02:41 AM
Post: #2
RE: Random Integers, No Repeats
(08-09-2023 02:30 AM)lrdheat Wrote:  I cannot remember how to generate random numbers from x to y with no repeats…anybody know how to accomplish this using the RANDINT or randint command?

You could create an array of y-x+1 elements, then generate a random integer in that range and if the corresponding element is 0, then it's a unique number. If so, append the number to a list and fill that element of the array with a non-zero. Once all the array is filled, you'll have your list.

Tom L
Cui bono?
Find all posts by this user
Quote this message in a reply
08-09-2023, 03:15 AM (This post was last modified: 08-09-2023 10:23 AM by Albert Chan.)
Post: #3
RE: Random Integers, No Repeats
The algorithm is called Fisher–Yates shuffle, with time complexity of O(n)
It is implemented in Python random.shuffle

HP Prime has it builtin:

CAS> shuffle([1,3,5,7,9])      → [5,1,9,3,7]
CAS> shuffle(5)                    → [2,5,3,4,1]
Find all posts by this user
Quote this message in a reply
08-09-2023, 04:54 AM
Post: #4
RE: Random Integers, No Repeats
(08-09-2023 02:30 AM)lrdheat Wrote:  I cannot remember how to generate random numbers from x to y with no repeats…anybody know how to accomplish this using the RANDINT or randint command?

If you don't mind using an undocumented but stable CAS function, rand(X,Y,Z) returns X random integers between Y and Z without repeats. Example: rand(10,50,59) returns all 10 integers between 50 and 59 in random order. It's faster than creating an array and then shuffling it. rand(10000,1,10000) takes only 0.0072 seconds on a G2 Prime. Although it's a CAS function, it also seems to work in Home and in non-CAS programs.

<0|ɸ|0>
-Joe-
Visit this user's website Find all posts by this user
Quote this message in a reply
08-09-2023, 01:24 PM
Post: #5
RE: Random Integers, No Repeats
Thanks, Joe! I had forgotten about rand().
Find all posts by this user
Quote this message in a reply
08-09-2023, 03:50 PM
Post: #6
RE: Random Integers, No Repeats
(08-09-2023 04:54 AM)Joe Horn Wrote:  ... rand(X,Y,Z) returns X random integers between Y and Z without repeats. Example: rand(10,50,59) returns all 10 integers between 50 and 59 in random order. It's faster than creating an array and then shuffling it.

I would bet that rand uses the Fisher-Yates algorithm internally. The G2 is very fast and so is Fisher-Yates.
Find all posts by this user
Quote this message in a reply
08-09-2023, 04:59 PM
Post: #7
RE: Random Integers, No Repeats
(08-09-2023 04:54 AM)Joe Horn Wrote:  
(08-09-2023 02:30 AM)lrdheat Wrote:  I cannot remember how to generate random numbers from x to y with no repeats…anybody know how to accomplish this using the RANDINT or randint command?

If you don't mind using an undocumented but stable CAS function, rand(X,Y,Z) returns X random integers between Y and Z without repeats. Example: rand(10,50,59) returns all 10 integers between 50 and 59 in random order. It's faster than creating an array and then shuffling it. rand(10000,1,10000) takes only 0.0072 seconds on a G2 Prime. Although it's a CAS function, it also seems to work in Home and in non-CAS programs.

Hey Joe, this is a great function. Do you happen to know what kind of seed is rand using?
Thanks and regards
Find all posts by this user
Quote this message in a reply
08-09-2023, 05:03 PM
Post: #8
RE: Random Integers, No Repeats
(08-09-2023 03:50 PM)John Keith Wrote:  I would bet that rand uses the Fisher-Yates algorithm internally.

Yes. We need n-1 random numbers, O(n) is as good as we can get.

Conversely, for list x to y, shuffled, number of swaps to restore it is also O(n)
(assume we don't cheat, and just return new list x to y)

We can think of this kind of sort as inverse Fisher-Yates.

Example, Fifteen Puzzle Game Solvability in O(n).
Find all posts by this user
Quote this message in a reply
08-09-2023, 05:10 PM
Post: #9
RE: Random Integers, No Repeats
(08-09-2023 04:59 PM)nickapos Wrote:  
(08-09-2023 04:54 AM)Joe Horn Wrote:  If you don't mind using an undocumented but stable CAS function, rand(X,Y,Z) returns X random integers between Y and Z without repeats. Example: rand(10,50,59) returns all 10 integers between 50 and 59 in random order. It's faster than creating an array and then shuffling it. rand(10000,1,10000) takes only 0.0072 seconds on a G2 Prime. Although it's a CAS function, it also seems to work in Home and in non-CAS programs.

Hey Joe, this is a great function. Do you happen to know what kind of seed is rand using?
Thanks and regards

No idea. The randseed() function doesn't seem to have any effect on the output of rand(X,Y,Z). Perhaps Bernard Parisse, who created Prime's CAS, can give us the details of how rand(X,Y,Z) works.

<0|ɸ|0>
-Joe-
Visit this user's website Find all posts by this user
Quote this message in a reply
08-09-2023, 05:21 PM
Post: #10
RE: Random Integers, No Repeats
srand(intiger) inititizes the rand() function
Find all posts by this user
Quote this message in a reply
08-09-2023, 05:26 PM (This post was last modified: 08-09-2023 05:27 PM by roadrunner.)
Post: #11
RE: Random Integers, No Repeats
umm, that would be initializes
and integer
Find all posts by this user
Quote this message in a reply
08-09-2023, 05:31 PM (This post was last modified: 08-09-2023 05:34 PM by Joe Horn.)
Post: #12
RE: Random Integers, No Repeats
(08-09-2023 05:21 PM)roadrunner Wrote:  srand(integer) initializes the rand() function

Awesome! Thanks!

Here's some more info about the rand(X,Y,Z) function from Bernard's documentation for XCAS:

Bernard Wrote:The rand command can also choose elements without replacement. If you give rand three integer arguments, rand(p,n1,n2) then it will return p distinct random integers from n1 to n2.
If you enter rand(2,1,10) for example, you will get 2 distinct random numbers from 1 to 10; perhaps [2,9].

You can also choose (without replacement) random elements of a given list. For this, you give rand a postive integer n and a list L; rand(n,L) will then return n random elements from the list.
If you enter rand(3,["a","b","c","d","e","f","g","h"]) you might get ["c","b","e"].
The list can have repeated elements; if you enter rand(4,["r","r","r","r","v","v","v"]) you might get ["v","v","r","v"].

<0|ɸ|0>
-Joe-
Visit this user's website Find all posts by this user
Quote this message in a reply
08-09-2023, 06:04 PM
Post: #13
RE: Random Integers, No Repeats
(08-09-2023 05:31 PM)Joe Horn Wrote:  
(08-09-2023 05:21 PM)roadrunner Wrote:  srand(integer) initializes the rand() function

Awesome! Thanks!

Here's some more info about the rand(X,Y,Z) function from Bernard's documentation for XCAS:

Bernard Wrote:The rand command can also choose elements without replacement. If you give rand three integer arguments, rand(p,n1,n2) then it will return p distinct random integers from n1 to n2.
If you enter rand(2,1,10) for example, you will get 2 distinct random numbers from 1 to 10; perhaps [2,9].

You can also choose (without replacement) random elements of a given list. For this, you give rand a postive integer n and a list L; rand(n,L) will then return n random elements from the list.
If you enter rand(3,["a","b","c","d","e","f","g","h"]) you might get ["c","b","e"].
The list can have repeated elements; if you enter rand(4,["r","r","r","r","v","v","v"]) you might get ["v","v","r","v"].
Beautiful thank you very much everyone
Find all posts by this user
Quote this message in a reply
08-09-2023, 06:09 PM
Post: #14
RE: Random Integers, No Repeats
The low-level algorithm source code is as follow:
Code:

  void shuffle(vector<int> & temp,GIAC_CONTEXT){
    int n=int(temp.size());
    // source wikipedia Fisher-Yates shuffle article
    for (int i=0;i<n-1;++i){
      // j ← random integer such that i ≤ j < n
      // exchange a[i] and a[j]
      int j=int(i+(giac_rand(contextptr)/double(rand_max2))*(n-i));
      std::swap(temp[i],temp[j]);
    }
  }

  vector<int> rand_k_n(int k,int n,bool sorted,GIAC_CONTEXT){
    if (k<=0 || n<=0 || k>n)
      return vector<int>(0);
    if (//n>=65536 && 
    k*double(k)<=n/4){
      vector<int> t(k),ts(k); 
      for (int essai=20;essai>=0;--essai){
    int i;
    for (i=0;i<k;++i)
      ts[i]=t[i]=int(giac_rand(contextptr)/double(rand_max2)*n);
    sort(ts.begin(),ts.end());
    for (i=1;i<k;++i){
      if (ts[i]==ts[i-1])
        break;
    }
    if (i==k)
      return sorted?ts:t;
      }
    }
    if (k>=n/3 || (sorted && k*std::log(double(k))>n) ){
      vector<int> t; t.reserve(k);
      // (algorithm suggested by O. Garet)
      while (n>0){
    int r=int(giac_rand(contextptr)/double(rand_max2)*n);
    if (r<n-k) // (n-k)/n=proba that the current n is not in the list
      --n;
    else {
      --n;
      t.push_back(n);
      --k;
    }
      }
      if (sorted)
    reverse(t.begin(),t.end());
      else
    shuffle(t);
      return t;
    }
    vector<bool> tab(n,true);
    vector<int> v(k);
    for (int j=0;j<k;++j){
      int r=-1;
      for (;;){
    r=int(giac_rand(contextptr)/double(rand_max2)*n);
    if (tab[r]){ tab[r]=false;  break; }
      }
      v[j]=r;
    }
    if (sorted)
      sort(v.begin(),v.end());
    return v;
  }
Find all posts by this user
Quote this message in a reply
09-05-2023, 08:51 AM
Post: #15
RE: Random Integers, No Repeats
I think the family of linear congruential generators (LCG) can be used to generate a sequence of numbers (they're not very random though). For example, this will generate the numbers between 0-15 in a pseude random order, twice (C#):

Code:

void Main()
{
    byte x = 15;
    byte a = 13;
    byte b = 5;
    for (int i = 0; i < 32; i++)
    {
        x = (byte)((x * a + b) & 0xF);
    }
}

2xHP48GX, HP 50g, two Retrotronik ram cards, DM42
/Daniel Lidström
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 2 Guest(s)