Random Integers, No Repeats

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