I rhink to avoid collisions altogether we should generate an ordered
sequence , in a dec. or inc. order and
display them randomly, i mean:
Let say a[10] contains all the random no.s , map all the 10 indexes to
a hash table and then display the arrays with the hashed index...
I think it may work...
what say..?
On 8/5/11, Gaurav Menghani <gaurav.mengh...@gmail.com> wrote:
> 1. Get a good seed.
> 2. Increase the degree of the polynomial.
>
> This is no fixed algorithm, if you find that more than T steps have
> passed and a new number has not been generated, you can always change
> the polynomial. And, please remember it is a 'pseudo-random number
> generator'. You can read the theory about PRNGs and LFSRs, all of them
> repeat.
>
> On Fri, Aug 5, 2011 at 7:14 PM, payel roy <smithpa...@gmail.com> wrote:
>> 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.
>>
>
>
>
> --
> 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.
