Write a method to shuffle a deck of cards. It must be a perfect shuffle - in other words, each 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect.

Basic Idea is run around random number generator & we need to take care of that so before moving forward we need to understand how random number generation works 

lets say you wants to generate random number between i to j e.g.
[ i,j ) excluding upper limit. One standard pattern for accomplishing this is:

Min + (int)(Math.random() * ((Max - Min) + 1))

The java Math library function Math.random() generates a double value in the range [0,1). Notice this range does not include the 1.


In order to get a specific range of values first you need to multiply by the magnitude of the range of values you want covered.

Math.random() * ( Max - Min )

This returns a value in the range [0,Max-Min).


For example if you want [5,10] you need cover 5 integer values so you use

Math.random() * 5 This would return a value in the range [0,5)

Now you need to shift this range up to the range that you are targeting. You do this by adding the Min value.

Min + (Math.random() * (Max - Min))

You now will get a value in the range [Min,Max). Following our example, that means [5,10):

5 + (Math.random() * (10 - 5))

But, this is still doesn't include Max and you are getting a double value.
In order to get the Max value included, you need to add 1 to your range parameter (Max - Min) and then truncate the decimal part by casting to an int. This is accomplished via:

Min + (int)(Math.random() * ((Max - Min) + 1))

And there you have it. A random integer value in the range [Min,Max],
or per the example [5,10]:

5 + (int)(Math.random() * ((10 - 5) + 1))

Algorithm:

This is a very well known algorithm known as Knuth-Shuffle. If you aren’t one

of the lucky few to have already know this algorithm, read on.Let’s start 

with a brute force approach: we could randomly selecting items and put them 

into a new array. We must make sure that we don’t pick the same item twice 

though by somehow marking the node as dead.
 

Array: [1] [2] [3] [4] [5]
Randomly select 4: [4] [?] [?] [?] [?]
Mark element as dead: [1] [2] [3] [X] [5]
 

The tricky part is, how do we mark [4] as dead such that we prevent that 

element from being picked again? One way to do it is to swap the now-dead [4]

with the first element in the array:
 

Array: [1] [2] [3] [4] [5]
Randomly select 4: [4] [?] [?] [?] [?]
Swap dead element: [X] [2] [3] [1] [5]
 

Array: [X] [2] [3] [1] [5]
Randomly select 3: [4] [3] [?] [?] [?]
Swap dead element: [X] [X] [2] [1] [5]
 

By doing it this way, it’s much easier for the algorithm to "know" that the 

first k elements are dead than that the third, fourth, nineth, etc elements 

are dead. We can also optimize this by merging the shuffled array and the 

original array.
 

Randomly select 4: [4] [2] [3] [1] [5]
Randomly select 3: [4] [3] [2] [1] [5]

Working Solution: Its Totally Worthy & Pure Shuffle Used in Our Music Player

class random
{
 
public static void shuffleArray(int[] cards) 
{
 int temp, index;int ar[]=new int[cards.length];
 int count=0;
 for (int i = 0; i < cards.length; i++)
 {
 index = (int) (Math.random() * (cards.length - i)) + i; 
//generate random index between i to n here we don't need to add 1 in last 
//to range as array indexes start at 0 if we add 1 to cards.length-i then 
//we might get index > n-1 which throws array out of index bound exception
 ar[count++]=index;
 temp = cards[i];
 cards[i] = cards[index];
 cards[index] = temp;
 }
  
 for(int i=0;i<ar.length;i++)
   System.out.print(ar[i] + " ");
}
 
public static void main(String a[])
 
{  int ar[]=new int[]{1,2,3,4,5};
    shuffleArray(ar);
      System.out.println();
   for(int i=0;i<ar.length;i++)
   System.out.print(ar[i] + " " );
}
 
}
 

Time Complexity: O(N)

Space Complexity: O(1)

Run Here https://ideone.com/UTk9V 

               https://ideone.com/B0YEn - Read from Consol