[Solved]: What's a uniform shuffle?

Problem Detail: 

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);     } } 

Asked By : morfioce

Answered By : Andrej Bauer

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$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47338