following solution should work but it uses an array so its ST is O(N)
#include <stdio.h>
#include <time.h>
#define MAX 500
/** copied from wikipedia
*
*/
unsigned m_w = time(NULL); /* must not be zero */
unsigned m_z = 300; /* must not be zero */
unsigned long get_random()
{
m_z = 36969 * (m_z & 65535) + (m_z >> 16);
m_w = 18000 * (m_w & 65535) + (m_w >> 16);
return (m_z << 16) + m_w; /* 32-bit result */
}
// CLRS
void randomize(int list[],int size){
for(int i=0;i<size;i++){
int rand = i+get_random()%(size-i);
// swap
int tmp = list[i];
list[i] = list[rand];
list[rand] = tmp;
}
}
int main(){
int A[MAX];
int N,M; // assuming N<MAX , M<N
scanf("%d",&N);
scanf("%d",&M);
for(int i=0;i<N;i++){
A[i]=i;
}
randomize(A,N);
for(int i=0;i<M;i++){
printf("%d ",A[i]);
}
}
On Mon, Aug 8, 2011 at 6:02 PM, Gaurav Menghani
<gaurav.mengh...@gmail.com>wrote:
> "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, 석문기 <smgs2...@gmail.com> wrote:
> > Box-muller method is the good solution without a lot of computation
> overhead
> >
> > 2011/8/8 Puneet Gautam <puneet.nsi...@gmail.com>
> >>
> >> 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 <puneet.nsi...@gmail.com> 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 <gaurav.mengh...@gmail.com> 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
> >> >> <puneet.nsi...@gmail.com>
> >> >> 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 <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.
> >> >>>
> >> >>>
> >> >>
> >> >>
> >> >>
> >> >> --
> >> >> 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.
> >>
> >
> > --
> > 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.
