7
$\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$
4
  • 2
    $\begingroup$ No, and this is a typical mistake people make when they try to shuffle. $\endgroup$ Commented Sep 19, 2015 at 9:16
  • 1
    $\begingroup$ Related question $\endgroup$
    – Raphael
    Commented Sep 19, 2015 at 9:53
  • 1
    $\begingroup$ See also here $\endgroup$
    – A.Schulz
    Commented Sep 19, 2015 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
    Commented Jan 15, 2017 at 23:31

3 Answers 3

16
$\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$
16
  • 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$ Commented Sep 19, 2015 at 10:40
  • 1
    $\begingroup$ The algorithm you describe seems to be due to Fisher and Yates. $\endgroup$ Commented Sep 19, 2015 at 18:14
  • 4
    $\begingroup$ ITYM “is wasteful, but most importantly it is not uniform” $\endgroup$ Commented Sep 19, 2015 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$ Commented Sep 19, 2015 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
    Commented Sep 19, 2015 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$
1
  • 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
    Commented Sep 19, 2015 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$
4
  • $\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
    Commented Jan 17, 2017 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
    Commented Jan 17, 2017 at 1:34
  • $\begingroup$ @Evil It generates twice as many and still does not have full coverage. $\endgroup$
    – paparazzo
    Commented Jan 17, 2017 at 2:06
  • $\begingroup$ That is definitely pseudocode, thanks! $\endgroup$
    – Raphael
    Commented Jan 17, 2017 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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