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.
