Generate uniqe 'random' int values for given interval

Question

I need to generate 'random' int values that will be used as array indexes so they need to be uniqe for given interval.

LFSR seems to be perfect for this task but theres a catch: either array size ought to have size 2^n (in some cases it forces to allocate much more memory than required one(eg. data size 2100 - array size 4096)) or to skip generated numbers until proper value is found (waste of LFSR capabilities, in some cases generation time of index can be noticeable).

I have tried to create some formula to compute array indexes but I've failed, especially for small (<120) array sizes.

Is there any optimal (in terms of resources and computing time) solution to this problem?

Thanks in advance for answers!

If you have a permutation of 2^n elements you can simply repeat that permutation until you get back into the desired subinterval. This requires less than two iterations on average. — CodesInChaos, Nov 06 '13 at 18:38
Related: http://stackoverflow.com/questions/686353/c-random-float-number-generation/686373#686373 — John Dibling, Nov 06 '13 at 19:01

score 0 · Answer 1 · answered Nov 06 '13 at 18:49

May be it help you.

#include <iostream>
#include <vector>

#include <cstdlib>
#include <cstring>
#include <ctime>

std::vector<int> random_interval_values(int b, int e)
{
    int n = e - b;

    std::vector<int>result(n);

    for(int i = 1; i < n ; ++i)
    {
         int t = rand() % i; // t - is random value in [0..i)
         result[i] = result[t]; // i-th element assigned random index-th value
         result[t]  =i;        // and, random position assigned i value

    }

    // increment all values to b.
    for(int i = 0; i < n; ++i) result[i] += b;

    return result;
}

int main()
{

   srand( time (NULL )) ;

   int interval_begin = 7;
   int interval_end   = 15;
    // [ interval_begin ... interval_end )  


   std::vector<int> v = random_interval_values( interval_begin, interval_end);

   for(int i= 0; i < v.size(); ++i)
     std::cout << v[i] << ' ';

  std::cout << std::endl;
}

Generate uniqe 'random' int values for given interval

1 Answers1