Random Shuffle.

Shuffle an array of size n such that each element has 1/n probability to remain in its original spot. The best solution has O(n) complexity.


Approach:
Use fisher-yates-knuth algorithm.
Let Array be A.
int len = A.length;
for (int i=len-1; i>=0; i--) {
int r = random()%(i+1);
swap(A[i],A[r]);
}


nth position can be taken by any of the n elements, since we are generating random number between 1 and n.
We can prove by induction that above holds true for n-1 and subsequent n-i for i<len and i>=0;


Code input/output:
printing original array: 
1 2 3 4 5 6 7 
printing shuffled array: 
4 3 2 1 7 6 5