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" <dond...@gmail.com <javascript:>> 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 algogeeks+...@googlegroups.com <javascript:>.
>>
>
--
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 algogeeks+unsubscr...@googlegroups.com.
