# Shuffling cards (a list of integers)

1. Nov 2, 2013

### divB

Hi,

I found this problem along with the solution:

"Given  an  array  of  distinct  integers,  give  an  algorithm  to  randomly  reorder  the integers  so  that  each  possible  reordering  is  equally  likely.   In  other  words,  given  a deck  of  cards,  how  can  you  shuffle  them  such  that  any  permutation  of  cards is equally  likely?
Good  answer:  Go  through  the  elements  in  order,  swapping  each  element  with  a random  element  in  the  array  that  does  not  appear  earlier  than  the  element.   This takes  O(n)  time.
Note  that  there  are  several  possible  solutions  to  this  problem,  as  well  as  several good‐looking  answers  that  are  incorrect.   For  example,  a  slight  modification  to  the
above  algorithm  where by  one  switches  each  element  with  any  element  in  the  array
does  not  give  each  reordering  with  equally  probability."

I don't understand why this extra step "does not appear earlier" should be required?

I would have created a random permutation of the indexes, and re-ordered the array according these indexes. E.g., from MATLAB:
Code (Text):

% "array" contains my list of distinct integers
shuffle_indexes = randperm(length(array));
shuffled_array = array(shuffle_indexes);

I don't see why this should be biased in any way when the random permutation is completely random.

Thanks

2. Nov 2, 2013

### AlephZero

Your Matlab code is not the same as the "good" algorithm you were given, because it conceptually does al the swaps "at once" not sequentially. I think the Matlab algorithm does solve the problem correctly - so long as the randperm function is implemented properly.

To see why "does not appear earlier" is required, work through the probabilities of the numbers being where they are, after each step.

After step 1, the first element has probability 1/n of having whatever value it has, and elements 2...n all have probability (n-1)/n.

After step 2, the second element has probability (n-1)/n x (1/(n-1) = 1/n of having whatever value it has, and elements 3...n have probability (n-1)/n x (n-2)(n-1) = (n-2)/n.

After (n-1) steps that gives what you want. Analyzing the version without "does not appear earlier" will show you why it is different.

A different way to see it is that the algorithm you were given is the same as:
"Put all the numbers in to a bag. Pick one from the bag at random and put it in position 1 in the array. Pick another number from the numbers left in the bag and put in in position 2. Repeat till done."

Or, if you don't like probabilities, just work through the algorithms on a list of length 3, and see what happens. There are 6 possible orders. The "does not appear earlier" version has exactly one way to produce each of them. Without "does not appear earlier", there are different numbers of ways to end up with different orders.

Last edited: Nov 2, 2013