Playing card shuffle goodness

Explanation

Monte Carlo simulations for comparing the efficiency of algorithms that may be executed manually without electronics for shuffling a deck of playing cards and for determining how well a shuffle was executed. The starting vector contains the ascending sequence numbered 1..52.

Please see the source code of each algorithm in the following text box for implementation details of each metric and shuffle algorithm. You can modify any argument or constant to see its effect after pressing the `Run` button. You can pick a deterministic random seed (`o.seed`), change the number of cards in a deck (`o.cards`), adjust the dimensions of a chart (`o.columns` and `o.bins`) or increase `o.samples` to trade off variance for speed. References:

Shuffling algorithms

Creates a random permutation by altering the order of elements within the sequence:

Fisher-Yates: well known and proven to produce an unbiased permutation on computers by optionally swapping each element by a random remaining element.
Riffle pair swap: mimics the popular two-hand leafing motion. Splits the deck in half, interleaves the halves and randomly decide whether to swap each aligned pair or not.
Riffle pick: a different model of the same motion. Splits the deck in half, and then picks randomly which half to take the next element from.
Gilbert-Shannon-Reeds riffle: an unbiased version that applies a binomial split to the deck and makes each pick in proportion to the number of cards remaining in each deck.
Inverse riffle: assign each card to one of two decks based on a coin flip and concatenate the decks.
Overhand: mimics the common hand motion of reversing small packets of random size by moving them from the top of the old deck to the top of the new deck.
Coin split: assign each card to either the earlier or the later deck by a random coin flip. Shuffle each deck by the same algorithm. Concatenate the earlier deck with the later deck.
Dice book: place each card inside a book in one of 36 slots decided by two dice throws. For example, after the page numbered twice the two throws concatenated: 22..132. Then go through each page in sequence and add each card to the output which was alone on their page. Collect all remaining cards to a separate deck and shuffle by the same algorithm.
Wandering dice: arrange all cards in a pseudo-grid. Hold onto the first one. Throw the dice twice and use them as coordinates towards the right and below (modulo) of the empty place to pick a card to place into the empty place from. Repeat as many times as required, preferably at least twice the number of cards. Finally place the card you hold to the empty place.

Metrics

Each metric estimates on a different scale how much the vector is different from the ascending sequence:

Rising: the number of rising subsequences within the sequence, each is a maximal disjoint subset whose elements are in sequence.
Neighbor swap: the number of neighboring elements which are out of order.
Neighbor offset: the average of modulo offset that is added to an element and its neighbor (or second neighbor, respectively).
Neighbors near: the number of elements for which 1 or 2 needs to be added (or subtracted) to arrive at its neighbor
Orbital cycles: the number of distinct cycles that result from determining the fixed point at each element. The value of an element will determine the index to look up next in an orbit until a loop is found.
Distance: the average of the distance from the location of a value to its location in the ascending sequence.
Offset: the average of the modulo offset to add to the original location of a value in the ascending sequence to arrive at its present location.
Inversion: the inversion number of the permutation (the number of pairs of elements which are out of order to each other) divided by the number of elements.
McGrath guess next: the number of correct guesses of the next card to be the first of the longest consecutive sequence in the remaining cards.

Requirements

You can install a web browser that supports at least JavaScript 1.0 (1995) to run this application or you may consider implementing a GemiWeb0 browser with JavaScript0 yourself according to the following specification:

bkil.gitlab.io/gemiweb0

'use strict';
function fisherYatesShuffle(v) {
  var n = v.length;
  var m = n - 1;
  var i = -1;
  while (m > (i = i + 1)) {
    swap(v, i, i + getRandom(n - i));
  }
}

function rifflePairSwapShuffle(v) {
  var n = v.length;
  intersperseFaroHalves(v);
  var i = -2;
  while (n > (i = i + 2)) {
    if (getRandomBits(1)) {
      swap(v, i, i + 1);
    }
  }
}

function rifflePairSwap6Shuffle(v) {
  var i = 7;
  while (i = i - 1) {
    rifflePairSwapShuffle(v);
  }
}

function rifflePickShuffle(v) {
  var n = v.length;
  var m = n >> 1;
  var u = new Array;
  var j = -1;
  var w = new Array;
  var k = -1;

var i = -1;
  while (m > (i = i + 1)) {
    u[j = j + 1] = v[i];
    w[k = k + 1] = v[i + m];
  }
  m = j;
  var q = k;
  j = -1;
  k = -1;

var i = -1;
  while (n > (i = i + 1)) {
    if ((k >= q) || ((m > j) && getRandomBits(1))) {
      v[i] = u[j = j + 1];
    } else {
      v[i] = w[k = k + 1];
    }
  }
}

function rifflePick6Shuffle(v) {
  var i = 7;
  while (i = i - 1) {
    rifflePickShuffle(v);
  }
}

function inverseRiffle6Shuffle(v) {
  var i = 7;
  while (i = i - 1) {
    inverseRiffleShuffle(v);
  }
}

function riffleGilbertShannonReedsShuffle(v) {
  var n = v.length;
  var m = 1;
  var i = n + 1;
  while (i = i - 1) {
    if (getRandomBits(1)) {
      m = m + 1;
    }
  }

var u = new Array;
  var j = -1;
  var w = new Array;
  var k = -1;
  i = -1;
  while (m = m - 1) {
    u[j = j + 1] = v[i = i + 1];
  }
  while (n > (i = i + 1)) {
    w[k = k + 1] = v[i];
  }
  m = j;
  var q = k;

j = -1;
  k = -1;
  var i = -1;
  while (n > (i = i + 1)) {
    if ((k >= q) || ((m > j) && ((m-j) > getRandom((q-k) + (m-j))))) {
      v[i] = u[j = j + 1];
    } else {
      v[i] = w[k = k + 1];
    }
  }
}

function riffleGilbertShannonReeds6Shuffle(v) {
  var i = 7;
  while (i = i - 1) {
    riffleGilbertShannonReedsShuffle(v);
  }
}

function overhand6Shuffle(v) {
  var i = 7;
  while (i = i - 1) {
    overhandShuffle(v);
  }
}

function wanderingDiceShuffle(v) {
  var n = v.length;
  var i = n + n + 1;
  var j = 0;
  var k;
  while (i = i - 1) {
    swap(v, j, k = (j + getRandom(36)) % n);
    j = k;
  }
}

n = u.length;
  j = -1;
  while (n > (j = j + 1)) {
    v[i = i + 1] = u[j];
  }

n = w.length;
  k = -1;
  while (n > (k = k + 1)) {
    v[i = i + 1] = w[k];
  }
}

function coinSplitShuffle(v) {
  coinSplitShuffle0(coinSplitShuffle0, v);
}

while (todos) {
      bin = bins[getRandom(36)];
      bin[bin.length] = todo[todos = todos - 1];
    }
  }
}

function offsetMetric(v) {
  var n = v.length;
  var s = 0;
  var i = -1;
  while (n > (i = i + 1)) {
    s = s + (((i + n + 1) - v[i]) % n);
  }
  return (s / n) | 0;
}

function neighborSwapMetric(v) {
  var n = v.length;
  var s = 0;
  var i = 0;
  while (n > (i = i + 1)) {
    if (v[i-1] > v[i]) {
      s = s + 1;
    }
  }
  return s;
}

function neighborOffsetMetric(v) {
  var n = v.length;
  var s = 0;
  var i = 0;
  while (n > (i = i + 1)) {
    s = s + ((n + (v[i] - v[i-1])) % n);
  }
  return (s / (n - 1)) | 0;
}

function neighbor2OffsetMetric(v) {
  var n = v.length;
  var s = 0;
  var i = 1;
  while (n > (i = i + 1)) {
    s = s + ((n + (v[i] - v[i-2])) % n);
  }
  return (s / (n - 2)) | 0;
}

function mcGrathGuessNextMetric(v) {
  var s = 0;
  var n = v.length;
  var seen = new Array;
  var real;
  var guess;
  var longestLen = 0;
  var len;
  var j;

var i = -1;
  while (n > (i = i + 1)) {
    guess = 0;

longestLen = 0;
    len = 0;
    j = -1;
    while (n > (j = j + 1)) {
      if (seen[j]) {
        if (len > longestLen) {
          guess = j - len;
          longestLen = len;
        }
        len = 0;
      } else {
        len = len + 1;
      }
    }
    if (len > longestLen) {
      guess = j - len;
    }

if (!(guess - (real = v[i] - 1))) {
      s = s + 1;
    }
    seen[real] = 1;
  }
  return s;
}

function runTests(o) {
  var m = new Object;
  m.rising = risingMetric;
  m.neighborSwap = neighborSwapMetric;
  m.neighborOffset= neighborOffsetMetric;
  m.neighbor2Offset = neighbor2OffsetMetric;
  m.neighborNear = neighborNearMetric;
  m.orbitalCycles = orbitalCyclesMetric;
  m.distance = distanceMetric;
  m.offset = offsetMetric;
  m.inversion = inversionMetric;
  m.mcGrathGuessNext = mcGrathGuessNextMetric;
  o.metrics = m;

testShuffler(o, 'Fisher-Yates shuffle', fisherYatesShuffle);
  testShuffler(o, 'Gilbert-Shannon-Reeds riffle shuffle', riffleGilbertShannonReedsShuffle);
  testShuffler(o, 'Gilbert-Shannon-Reeds riffle shuffle 6 times', riffleGilbertShannonReeds6Shuffle);
  testShuffler(o, 'Inverse riffle shuffle', inverseRiffleShuffle);
  testShuffler(o, 'Inverse riffle shuffle 6 times', inverseRiffle6Shuffle);
  testShuffler(o, 'Riffle pair swap shuffle', rifflePairSwapShuffle);
  testShuffler(o, 'Riffle pair swap shuffle 6 times', rifflePairSwap6Shuffle);
  testShuffler(o, 'Riffle pick shuffle', rifflePickShuffle);
  testShuffler(o, 'Riffle pick shuffle 6 times', rifflePick6Shuffle);
  testShuffler(o, 'Overhand shuffle', overhandShuffle);
  testShuffler(o, 'Overhand shuffle 6 times', overhand6Shuffle);
  testShuffler(o, 'Coin split shuffle', coinSplitShuffle);
  testShuffler(o, 'Dice book shuffle', diceBookShuffle);
  testShuffler(o, 'Wandering dice shuffle', wanderingDiceShuffle);

var v = getSequence(o);
  testMetrics(o, 'Metrics of sequence', v);

var n = v.length;
  swap(v, 0, n - 1);
  testMetrics(o, 'Metrics of single swap', v);

var d = n >> 1;
  var i = d;
  while (i = i - 1) {
    swap(v, i, n - 1 - i);
  }
  testMetrics(o, 'Metrics of reverse', v);

i = d >> 1;
  while (i) {
    swap(v, i = i - 1, d - 1 - i);
  }
  testMetrics(o, 'Metrics of half reversed', v);

v = getSequence(o);
  i = d;
  while (i) {
    swap(v, i = i - 1, i + d);
  }
  testMetrics(o, 'Metrics of halves swapped', v);

v = getSequence(o);
  i = n;
  while (i) {
    swap(v, i = i - 1, i = i - 1);
  }
  testMetrics(o, 'Metrics of swapped neighbors', v);

i = d;
  while (i) {
    swap(v, i = i - 1, n - 1 - (i = i - 1));
  }
  testMetrics(o, 'Metrics of reversed interspersed', v);

v = getSequence(o);
  intersperseFaroHalves(v);
  testMetrics(o, 'Metrics of halves interspersed', v);
}

function tester() {
  var o = new Object;
  o.seed = 0;
  o.bins = 9;
  o.columns = 32;
  o.cards = 52;
  o.samples = 100;
  o.run = runTests;
  return o;
}

tester();

Shuffle and metrics scripts