Shuffling cards (a list of integers)

[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:

% "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

 

[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 into 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.