Shuffle algorithm is not a proper shuffle algorithm

[Ghostbird]

This is not a random shuffle algorithm:

bmm-web/plugins/mediaPlayer/Queue.ts

Line 47 in 284ec84

public shuffle() {

Proof

1. For an array of $n$ elements, there are exactly $n!$ permutations (i.e. possible shuffles).
2. Every comparison during a shuffle is a choice between two sets of permutations. For a random comparator, there is a $\frac{1}{2}$ chance of choosing each set.
3. For each permutation $p$, the chance of ending up with permutation $p$ is a fraction with denominator $2^k$ (for some $k$), because it is a sum of such fractions (e.g. $\frac{1}{8} + \frac{1}{16} = \frac{3}{16}$).
4. For $n = 3$, there are six equally-likely permutations. The chance of each permutation, then, is $\frac{1}{6}$. This can't be expressed as a fraction with a power of 2 as its denominator.
5. Therefore, the coin flip sort will never result in a fair distribution of shuffles.

Example

A short visualisation of the problem would be this:

Divide a cake among six people¹ but you can only do so by cutting a piece exactly into two equal halves². Either you'll end up with two extra pieces (eight equal pieces), or you'll end up with four smaller pieces and two bigger pieces³.

Other issues

The sort is not well-defined, as it generates a random number for each individual comparison. You could define a sort as completed when for every comparison between two adjacent elements, they are always correctly ordered. Mathematically this sort should never return and run forever. This proves that the actual result is heavily implementation dependent.

Proposed solution

Change it to a Schwartzian transform shuffle, I think the result will be just as good as Fisher-Yates used by the BMM app, but I think the algorithm is much easier to understand.

['A', 'B', 'C']
  // Wrap each entry and add a random sort number,
  // assume that the chance that two entries get exactly the same value is negligible
  .map((x) => ({ original: x, sort: Math.random() }))
  // Sort by the random numbers
  .sort((a, b) => (a.sort - b.sort))
  // Remove the random numbers and restore the original data
  .map(({ original }) => original);

Footnotes

1. Representing the six possible permutations of an array with three elements. ↩

2. Representing the 50% chance / coin flip implemented as random() - 0.5 ↩

3. This is what happens in practice, some permutations have higher chance of appearing than others. ↩