@don : awesome .... +1 . I was not aware of George Marsaglia's Multiply With Carry generator. But it is soo coooolll . If you have any good link for its proof or explanation of the idea behind it then please mention it. I never knew generating random number can be few lines of code :) Thanks :)
On Sat, Feb 8, 2014 at 1:28 AM, Don <[email protected]> wrote: > A random generator will not always (or even usually) produce a permutation > of the possible values before repeating. > If you call my function 10 million times and tally up the results, you > will get a distribution with about a million of each value, as close as you > would expect for a random sample. > Your question was to randomly generate values in the range 1-10, not to > generate permutations. > > Here is a way to generate a permutation without swapping: > > unsigned int X = time(0); > int n[10]; > n[0] = 10; > for(i = 1; i < 10; ++i) > { > X = 63663 * (X&65535) + (X>>16); > int j = (X & 65535) % (i+1); > n[i] = n[j]; > n[j] = i; > } > > // n now contains a permutation of the values 1-10. > > > On Thursday, February 6, 2014 11:33:53 PM UTC-5, atul007 wrote: > >> @don: algo look fine..i tested it ,but it did not generate 1-10 with >> probabilty of 1/10 everytime. >> actually question was asked in an intrview. >> question started with displaying all elements in an array randomly >> without repetition i.e only once( probabilty 1/10)...which can be done with >> fisher yates . >> then interviewer said that u are not allowed to swap elements which is >> requied in fishr yates. >> his hint was: how will you generate randomly number from 1-10 without use >> of rand() function. >> expected time complexity : O(n) >> On 7 Feb 2014 03:17, "Don" <[email protected]> wrote: >> >>> Just noticed that you asked for 1-10, and my code will clearly generate >>> 0-9. Add one for the desired range. >>> Don >>> >>> On Wednesday, February 5, 2014 4:29:26 PM UTC-5, Don wrote: >>>> >>>> // Using George Marsaglia's Multiply With Carry generator >>>> int rnd10() >>>> { >>>> static unsigned int x = time(0); >>>> x = 63663 * (x&65535) + (x>>16); >>>> return (x & 65535) % 10; >>>> } >>>> >>>> On Sunday, February 2, 2014 2:51:47 AM UTC-5, atul007 wrote: >>>>> >>>>> Generate random number form 1 - 10 with probability of 1/10.You are >>>>> not allowed to used rand() function. >>>>> >>>>> any simple way of achieving above with using any complex >>>>> implementation of random number generators algorithm . >>>>> >>>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to [email protected]. >>> >> -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
