## Shuffle a deck of cards perfectly

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.

My initial thoughts:
We first select a card randomly from the 52 cards. That is probability of 1/52. We then select another card from the rest 51 cards. That is probability of 1/51. So on and so forth. Finally we have a particular permutation with probability of 1/52!, which is expected.

My initial codes:

```	public static List<Integer> shuffle() {
Set<Integer> deck = new HashSet<Integer>();
// build a deck of cards
for (int i = 0; i < 52; ++i) {
}
List<Integer> shuffledDeck = new ArrayList<Integer>();

for (int i = 0; i < 52; ++i) {
int card;
do {
card = new Random().nextInt(52) + 1;
} while (!deck.contains(card));
deck.remove(card);
}
return shuffledDeck;
}

Solution:
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]

This is an easy algorithm to implement iteratively:
public static void shuffleArray(int[] cards) {
int temp, index;
for (int i = 0; i < cards.length; i++) {
index = (int) (Math.random() * (cards.length - i)) + i;
temp = cards[i];
cards[i] = cards[index];
cards[index] = temp;
}
}

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b2dea6d4f3d4', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b2dea6d4f424',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b2dea6d4f427',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});

Related
```