5
$\begingroup$

What does it mean exactly a "uniform shuffle" algorithm ?

Is this method considered a uniform shuffle ?

public void shuffle(Comparable[] a) {
    int n = a.length;
    int k, j;
    for (int i = 0; i < n; i++) {
        k = StdRandom.uniform(n); // k in [0, n-1]
        j = StdRandom.uniform(n); // j in [0, n-1]
        exch(a, j, k);
    }
}
$\endgroup$
  • 2
    $\begingroup$ No, and this is a typical mistake people make when they try to shuffle. $\endgroup$ – Andrej Bauer Sep 19 '15 at 9:16
  • 1
    $\begingroup$ Related question $\endgroup$ – Raphael Sep 19 '15 at 9:53
  • 1
    $\begingroup$ See also here $\endgroup$ – A.Schulz Sep 19 '15 at 10:20
  • $\begingroup$ That is not uniform. You would totally miss some i. You are better off swapping i with a random and even that is not uniform. $\endgroup$ – paparazzo Jan 15 '17 at 23:31
14
$\begingroup$

A uniform shuffle of a table $a = [a_0, ..., a_{n-1}]$ is a random permutation of its elements that makes every rearrangement equally probable. To put it in another way: there are $n!$ possible rearrangements of $n$ elements and you need to pick one of them uniformly at random.

Many methods for shuffling seem uniform to people but are not and so it is common to see them implemented badly. For instance, shuffling by repeatedly exchanging two randomly chosen elements, as in the question, is not uniform and is also wasteful, as it generates twice as many random numbers as necessary.

A simple algorithm for a uniform shuffle is this:

import random
def shuffle(a):
    n = len(a)
    for i in range(n-1):
        j = random.randint(i, n-1)
        (a[i], a[j]) = (a[j], a[i])

This works in time $\Theta(n)$ as follows: assuming $a_0, ..., a_{i-1}$ are already shuffled, randomly select an element $a_j$ among the remaining $a_i, ..., a_{n-1}$ and exchange it with $a_i$.

To see that the result is uniformly shuffled, observe that initially every element has $\frac{1}{n}$ chance to land in place $0$ and $\frac{n-1}{n}$ to land in one of the remaining places $1, \ldots, n-1$. Therefore place $0$ is uniformly shuffled. In the next step, every element has probability $\frac{1}{n-1} \cdot \frac{n-1}{n}$ to land in place $1$, because this happens when it is not placed at 0 (probabilty $\frac{n-1}{n}$) and it is selected to be at place 1 (probability $\frac{1}{n-1}$). We may proceed inductively: an element lands in place $i$ with probability $$\frac{n-1}{n} \cdot \frac{n-2}{n-1} \cdot \frac{n-3}{n-2} \cdot \cdots \cdot \frac{n-i}{n-i+1} \cdot \frac{1}{n-i} = \frac{1}{n}.$$ The first $i$ factors arise for an element not being placed anywhere among places $0, \ldots, i-1$, and the last one for it being chosen to be placed at $i$.

$\endgroup$
  • 1
    $\begingroup$ +1 but I can't agree that it's "more important" that the naive shuffle is wasteful than that it gives the wrong answer! $\endgroup$ – David Richerby Sep 19 '15 at 10:40
  • 1
    $\begingroup$ The algorithm you describe seems to be due to Fisher and Yates. $\endgroup$ – Nate Eldredge Sep 19 '15 at 18:14
  • 3
    $\begingroup$ ITYM “is wasteful, but most importantly it is not uniform” $\endgroup$ – Gilles Sep 19 '15 at 18:30
  • 1
    $\begingroup$ You people are such nitpicks. It's almost as if you're all some kind of mathematicians. I removed the controversial statement. $\endgroup$ – Andrej Bauer Sep 19 '15 at 20:34
  • 1
    $\begingroup$ @DavidRicherby Since the algorithm in question is more wrong and less efficient than other known algorithms, I don't think it's acceptable. $\endgroup$ – Raphael Sep 19 '15 at 22:16
7
$\begingroup$

As Andrej explains in his answer, a random shuffle consists of applying a uniformly random permutation on the input, or equivalent. Your algorithm, in contrast, applies $n$ random transpositions. This cannot possible produce an exact random shuffle, since the probability of each resulting permutation is of the form $A/n^{2n}$, which cannot equal $1/n!$.

However, if you continue to perform random transpositions, eventually you will reach a distribution which is very close to that of a random shuffle. How many exactly are needed? Diaconis and Shahshahani [1] showed that $(1/2)n\log n + \omega(n)$. After performing that many random transpositions, you reach a distribution which is $o(1)$-close to uniformly random (in an appropriate sense).

More accurately, if you perform $(1/2)n\log n + f(n)$ transpositions then the resulting sequence of distributions (one for each $n$) is $o(1)$-close to uniformly random if and only if $f(n) = \omega(n)$.


  1. Generating a random permutation with random transpositions by P. Diaconis and M. Shahshahani (1981)
$\endgroup$
  • 4
    $\begingroup$ Dear reader, please don't take this as "my algorithm is basically okay, I just need to make n a bit larger". This result is of theoretical interest only. In practice, if you want uniform shuffles just use a proper algorithm (which is also faster). $\endgroup$ – Raphael Sep 19 '15 at 17:21
0
$\begingroup$

This is a shuffle similar to what you have. If you go through the permutations you will find some shuffles are favored.

for (i is 1 to n)
  Swap i with random position between 1 and n

This was actually a error on a poker site poker site

It does not produce a uniform distribution
Consider all possible random

for (i is 1 to n)
    for (j is 1 to n)
         Swap i with j

This is just a simple 1, 2, 3.

permutation   count
312           4
321           4
123           4
231           5
213           5
132           5

It considers more flops / swaps than required and does not even have a uniform distribution.

Fisher Yates is considered uniform and efficient

$\endgroup$
  • $\begingroup$ I have no objections to your pseudocode, but the answer you provided is in my opinion the same as Andrej's, but he provided a proof not just link. I mean there is nothing new or different than already stated. $\endgroup$ – Evil Jan 17 '17 at 0:01
  • 1
    $\begingroup$ "For instance, shuffling by repeatedly exchanging two randomly chosen elements, as in the question, is not uniform and is also wasteful, as it generates twice as many random numbers as necessary." $\endgroup$ – Evil Jan 17 '17 at 1:34
  • $\begingroup$ @Evil It generates twice as many and still does not have full coverage. $\endgroup$ – paparazzo Jan 17 '17 at 2:06
  • $\begingroup$ That is definitely pseudocode, thanks! $\endgroup$ – Raphael Jan 17 '17 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.