"The space complexity is O(1)" I know about hash-tables. Can you implement with O(1) space complexity?
On Mon, Aug 8, 2011 at 10:56 AM, 석문기 <[email protected]> wrote: > Box-muller method is the good solution without a lot of computation overhead > > 2011/8/8 Puneet Gautam <[email protected]> >> >> 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. >> > > -- > 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.
