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] <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 [email protected] <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 [email protected].
