Hi,(adsbygoogle = window.adsbygoogle || []).push({});

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:

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

% "array" contains my list of distinct integers

shuffle_indexes = randperm(length(array));

shuffled_array = array(shuffle_indexes);

Thanks

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Shuffling cards (a list of integers)

**Physics Forums | Science Articles, Homework Help, Discussion**