You might want to read the theory on Pseudo-Random Number Generators
[0] and Linear Feedback Shift Register [1]
The basic way of generating a random number is taking up a polynomial,
f(x) = ax^n + bx^(n-1) + .. + yx + z, and finding f(i + seed) % N,
where i is the ith random number you want, and seed can be anything
random available, for example, you can find the current millisecond
using time.h functions.
A simple implementation, without the time thing is below:
#include<iostream>
using namespace std;
int poly[10],pn,N,M;
int get(int seed)
{
int t=0;
for(int i=0;i<pn;i++)
{
int res=poly[i];
for(int j=1;j<=(i+1);j++) { res = (res*seed); if(res>=N)
res%=N; }
t+=res;
if(t>=N) t%=N;
}
t=(t+seed);
t%=N;
return t;
}
void setup_prng()
{
pn=5;
poly[0]=2; poly[1]=3; poly[2]=5; poly[3]=7; poly[4]=11;
N=200; M=100;
}
int main()
{
setup_prng();
for(int i=1;i<=M;i++)
cout<<get(i)<<endl;
return 0;
}
Whenever there is a collision, you can increment the value passed to
the random number generator and continue. However, I am not sure how
to check for collisions in O(1) space.
[0] http://en.wikipedia.org/wiki/Pseudorandom_number_generator
[1] http://en.wikipedia.org/wiki/Linear_feedback_shift_register
On Fri, Aug 5, 2011 at 5:19 PM, payel roy <smithpa...@gmail.com> wrote:
> Given a range 0-N, generate 'M' random numbers from the range without any
> duplication. The space complexity is O(1).
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Gaurav Menghani
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
