./dev 
Original heme by orderedlist (CCBYSA)
Where applicable, all content is licensed under a CCBYSA.

The FisherYates shuffle algorithm is used to create a random permutation. The derivation is relatively straight forward:
function fisher_yates_shuffle(a) {
var t, n = a.length;
for (var i=0; i<(n1); i++) {
var idx = i + Math.floor(Math.random()*(ni));
t = a[i];
a[i] = a[idx];
a[idx] = t;
}
}
We choose the first element at random, then proceed to choose subsequent entries from the remaining elements.
As a spot check, we can confirm that there are $n!$ configurations yielding approximately $ n (lg(n)  1) $ bits of entropy. Each poll of the random number generator is for $ lg(ni) $ bits over $n1$ entries:
$$ lg(2) + lg(3) + \cdots + lg(n) = \sum_{k=1}^{n} lg(k) = lg(n!) $$
One can consider the following incorrect way to do the shuffle:
function nofish_shuffle(a) {
var t, n = a.length;
for (var i=0; i<n; i++) {
var idx = Math.floor(Math.random()*n);
t = a[i];
a[i] = a[idx];
a[idx] = t;
}
}
a slight variant:
function noyaks_shuffle(a) {
var t, n = a.length;
for (var i=0; i<n; i++) {
var idx = Math.floor(Math.random()*(n1));
if (idx==i) { idx = n1; }
t = a[i];
a[i] = a[idx];
a[idx] = t;
}
}
and another:
function nomaar_shuffle(a) {
var t, n = a.length;
for (var i=0; i<n; i++) {
var idx0 = Math.floor(Math.random()*n);
var idx1 = Math.floor(Math.random()*n);
t = a[idx0];
a[idx0] = a[idx1];
a[idx1] = t;
}
}
Where the difference in nofish_shuffle
and noyaks_shuffle
is to skip the current index when considering which element to permute.
nomaar_shuffle
is yet another variant where each two elements are
chosen at random and swapped $n$ times.
A friend of mine suggested an nice proof to show the above two shuffle algorithms provide incorrect results.
As above, there are $n!$ possible shuffles we want to choose from, with
equal probability.
Since nofish_shuffle
is choosing each element to permute from the whole
array, there are $n^n$ possible choices for the permutation, where
some permutations might be represented more than once.
Producing multiple configurations is permissible so long as nofish_shuffle
would produce an equal distribution for each of the $n!$ configurations.
Since $ n! \nmid n^n $ for $n>2$, there must be some configurations that
appear more often by the pigeonhole principle.
noyaks_shuffle
doesn't fare much better since there are $n^{n1}$ possible
choices of permutation schedules and $n! \nmid n^{n1}$ for $n>2$.
The same type of analysis works for the nomaar_shuffle
by noticing
that the number of permutation schedules is $n^{2 n}$ and that still $n! \nmid n^{2 n}$.
Though hidden in such a large configuration space, nofish_shuffle
,
noyaks_shuffle
and nomaar_shuffle
produce configurations that are not uniformly
distributed.