How do you guarantee termination of your algorithm if duplication occurs ??
On 5 August 2011 18:25, Gaurav Menghani <gaurav.mengh...@gmail.com> wrote:
> 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.
>
>
--
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.
