## Random Card Problem

Random Card Problem is quite popular in game company. I failed a phone interview a month ago because of this problem, so I search for the right answer and post here.

Problem statement is, design an algorithm so that you get a random placement of a set of n cards.

My original answer is as follows:

```
for each index i,
get a random index j,
change cards between i and j
```

However, this is wrong. To see why, let’s have a look at what a right answer looks like:

```
for each index i,
get a random index j from i to n,
change cards between i and j
```

There exist another good algorithm: we know each placement has a unique ID: its place in the whole possible placements. For example, assume n = 3, ID of ‘123’ is 1, ‘132’ is 2, ‘213’ is 3, ‘231’ is 4, ‘312’ is 5, and ‘321’ is 6. It is easy to get the placement from its ID, so we random an ID and get its placement.

#### Why my answer is wrong

From calculation, we know that, in the right solution, the probability a card stays in its original index is the same for each card, while it is not in my solution.

In the right solution, when i = 1, Pr(1st card stays in 1st place) = 1/n; when i = 2, Pr(2nd…) = (n - 1)/n * 1/(n - 1) = 1/n; when i = 3, Pr(3rd…) = … = 1/n…

Now you see why the right solution right, and you see why my solution wrong. I was surprised by the magical math here the first time I realized it.