You may be right..we cant remove collisions in O(1) time... But hey, hash table is still an effective way..
On 8/8/11, Puneet Gautam <[email protected]> wrote: > 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.
