# Using a Shuffle Algorithm on a Deck of Cards

### Shuffle a Deck of Cards

Let’s try to write a method which will shuffle a deck of cards. The deck should be perfectly mixed. The card permutations should be equally probable.

Solution

We will use the perfect random number generator. Let’s solve the problem using the most obvious way. We can select random cards and put them into a new deck. In fact, a deck is an array; therefore, we need a way to lock some particular elements.

Original deck     

/* Choose a random element to put it in the beginning of the shuffled deck */
/* Mark it in the original deck as “locked” so we will not take it again */

Shuffled deck  [?] [?] [?] [?]
Original deck    [X] 

If we mark item  will that prevent selecting it again? One way is to swap the “locked” () and the first elements of the deck:

Original deck     

/* Choose a random element to put it in the beginning of the shuffled deck and
change the current element with the 1st one */

Shuffled deck  [?] [?] [?] [?]
Original deck [X]    

/* Choose a random element to put it in the beginning of the shuffled deck
and change the current element with the 2nd one */

Shuffled deck   [?] [?] [?]
Original deck [X] [X]   

The algorithm is easier to implement for the situation where the first k cards are “locked” than for the situation where, for example, the third, fourth, and ninth cards are “locked”.

We can optimize the algorithm combining the shuffled and the original deck.

Original deck     

/* Choose a random element to put it between 1 and 5 and swap it with 1.
In this example we chose 4th;
after that, the 1st element is locked */

Original deck     

/* Element 1 is locked. Choose a random element to swap it with element 2.
In this case it will be number 3*/

Original deck     
/* repeat */

This algorithm is easy to implement iteratively:

```public void shuffle(int[] array) {
int tmp, number;
for (int i = 0; &lt; array.length; i++) {

number = (int) (Math.random() * (array.length - i)) + i;
tmp = array[i];
array[i] = array[number];
array[number] = tmp;
}
}
```