Hey avoiding collisions using hash table can be real easy : eg: if 192 is the no generated let it hash to say index 7 of hash table...so when it is again generated, it hashes to the same 7th index of hash table, but we have a non zero value already present at that index , 192 so we can reject this generated no. and proceed to the next one..
Whereas in an array , avoiding collision is a really hectic way...u need to scan all the previously generated no.s for duplicacy...well that aint gonna run in O(1) time.. So implementing hash table reduces that overhead and runs it in O(1) time..(it just has to check one if condition)....with a bigger constant. And moreover, we may even dont want an ordered sequence...just put the generated no.s in hash table as soon as they are generated...dats it.. then afterwards display that hash table.. Did u get me...? On 8/7/11, Gaurav Menghani <[email protected]> wrote: > We can have a sorted sequence and display them in random order, but > that is the same problem. How do we display them in random order? We > need to have a sequence of random indices, that is the same problem as > having random numbers, isn't it. > > Moreover, I don't think collisions can be avoided in less than O(n). > We can have an efficient hash-table, but I am not sure how it can be > done in O(1) or better. > > On Sat, Aug 6, 2011 at 12:37 PM, Puneet Gautam <[email protected]> > wrote: >> 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 <[email protected]> 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 <[email protected]> wrote: >>>> How do you guarantee termination of your algorithm if duplication occurs >>>> ?? >>>> >>>> On 5 August 2011 18:25, Gaurav Menghani <[email protected]> >>>> 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 <[email protected]> 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 [email protected]. >>>>> > To unsubscribe from this group, send email to >>>>> > [email protected]. >>>>> > 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 [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]. >>>>> 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 [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
