1
$\begingroup$

Given an array of integer numbers and random generator how to perfectly shuffle the array? "Perfectly" means that every permutation is equally likely. One solution is go from 1st element to last element and swap current element, say i-th, with randomly choose from range i, i+1, ..., n. This way it is easy to show that each element has probability 1/n to be in any place. For example lets choose number, say m. The probability of it to be in the position one is 1/n. probability of it to be in position 2 is $\frac{n-1}{n} \cdot \frac{1}{n-1}=\frac{1}{n}$ , and so forth.

My question is about another way to shuffle numbers. Going from 1 to n we swap current number with randomly chosen one from entire array. Does this algorithm guarantee that every permutation obtained this way is equally likely?

Thank you.

EDIT: I meant that we can swap card with itself. (entire is literally entire array)

  • 0
    shuffling a deck is just a name. I am interested in mathematical part. I named this way to attract attention :-)2012-12-06

2 Answers 2

2

Your algorithm does not work. The reason for this is quite simple: for any position $i$, you choose from $n-1$ cards to swap the card in that posiiton with - all the positions that are not $i$. So the set of choices that you make could be encoded as a sequence of $n$ integers, each in the set $\{ 1, 2, \ldots, n \}$ and with the $i$th such integer not equal to $i$; there are $(n-1)^n$ such sequences, all equally likely.

But you need the probability of a given permutation $\pi$ to be $1/n!$. That means that you need $(n-1)^n / n!$ of these sequences to give the permutation $\pi$. But $(n-1)^n / n!$ is not always an integer - for example when $n = 3$ it's $2^3 / 3! = 8/6 = 4/3$.

It might help to demonstrate this for $n = 3$. Consider the 3-tuple $(x_1, x_2, x_3)$, where $1 \le x_i \le 3$ for each $i$ and $x_i \not = i$. We'll swap the card in position $i$ with the card in position $x_i$. The possible sequences are $(2,1,1), (2,1,2), (2,3,1), (2,3,2), (3,1,1), (3,1,2), (3,3,1), (3,3,2)$ -- there are eight of them. Consider for example $(2,1,1)$. This says to swap positions 1 and 2, then 2 and 1, then 3 and 1; starting with $123$ you get $321$. In the end you get eight (non-distinct) orderings, so the probability of any order must be a multiple of $1/8$; but $1/6$ is not a multiple of $1/8$.

This is one of the common implementation errors for the Fisher-Yates shuffle, about which Jeff Atwood has compiled some interesting data.)

  • 0
    So now we just need $n^n/n!$ to not be an integer. It's not.2012-12-06
0

Here's an approach, not an answer: Card $1$ can end in first place either by swapping with itself and never getting picked, probability $\frac 1n(\frac {n-1}n)^{n-1}\approx \frac 1{(n-1)e}$ or by swapping with something, swapping back, and never being picked again with probability $\frac {n-1}{n^2}(\frac{n-1}n)^{n-2}\approx \frac 1{(n-1)e}$, or by swapping three or more times. Work in this manner and see if it adds to $\frac 1n$ in the limit of large $n$.