=>Take a function rand() which returns value between [0, 1) uniformly or use
function rand(n) = n*rand() which return value between 0- (n-1) using
uniform probability distribution.
=>Now create a array A[0..n-1] = [0..n-1]
now rake an array R.
k = n;
for(i = 0; i < n; i++){
a = rand(k);
R.push(A[a]);
swap(A[a], A[k-1]);
k--;
}
return(R);
Verification:
1.) Yes, R contains values between 0-n-1;
2.) Yes, R has no repeated numbers
3.) R can be filled in O(n) so yes deterministic time.
4.) Correlation factor: Selection of one number should not affect the
probability of selecting other number.
here correlation factor = 0;
for each location 0..n-1 the probability of putting any number is 1/n.
->At 0th index probability of putting a number say, x is: 1/n
->at 1st index probability of putting a number y is: (n-1)/n * 1/(n-1) =
1/n
->at 2nd index probability of putting a number z is: (n-1)/n *(n-2)/(n-1) *
1/(n-2) = 1/n
and so on. So selection of any number at any position is independent of any
number being selected. So
they have independent and uniform probability.
-Piyush
On Sat, Sep 17, 2011 at 10:42 PM, sivaviknesh s <sivavikne...@gmail.com>wrote:
> Write a method fill up an array of size n - and returns the array to the
> caller - with the following conditions
>
> 1. the numbers shud be between 0 to n-1
> 2. no repeated numbers
> 3. the method should have a deterministic time to fill the arrays
> 4. arrays returned from the method should have low-correlation factor
>
> ...btw what does 4 th point mean? what is a correlation factor?? Plz
> provide code and explain...
>
>
> --
> Regards,
> $iva
>
> --
> 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.
