Random Integers, No Repeats

[lrdheat]

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?

[toml_12953]

(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.

[Albert Chan]

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]

[Joe Horn]

(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.

[lrdheat]

Thanks, Joe! I had forgotten about rand().

[John Keith]

(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.

[nickapos]

(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

[Albert Chan]

(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).

[Joe Horn]

(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.

[roadrunner]

srand(intiger) inititizes the rand() function

[roadrunner]

umm, that would be initializes
and integer

[Joe Horn]

(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"].

[nickapos]

(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

[parisse]

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

[dlidstrom]

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