A CodePen by Gabriel Lesperance.

index.html

<label>Sequence Length: <input type='text' name='len' id='len' value=10 maxlength=3 size=3></label>
<a href='javascript:void(0)' onClick='shuffle()'>Shuffle</a>

Linear-Congruential-Generator-for-Efficient-Shuffle-of-Finite-Sequence.markdown

Linear Congruential Generator for Efficient Shuffle of Finite Sequence

A CodePen by Gabriel Lesperance.

script.js

function pow2roundup (x) {
  if (x < 0)
    return 0;
  --x;
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  
  return x+1;
}


// uses a Linear Congruential Generator to generate a seemingly random sequence of N 
// integers.
// https://en.wikipedia.org/wiki/Linear_congruential_generator
function do_shuffle(n) {
  var xi = Math.floor(Math.random() * n)
  
  var m = pow2roundup(n) * 2
  var c = Math.ceil(Math.random() * m)
  var a = Math.ceil(Math.random() * m)
  
  // Make sure `c` and `m` are coprime
  if (c % 2 == 0) c -= 1
  
  // Make sure `a - 1` is divisible by 4
  a = (a + 4 - (a % 4) + 1) % m
  
  function lcg(xi) {
    var val = (a*xi + c) % m;
    if (val < n) return val
    else return lcg(val)
  }
  
  $('body').append('<br/>')
  
  for (var i=0; i<n; i++) {
    xi = lcg(xi)
    $('body').append($('<span>' + xi + (i + 1 != n ? '-' : '') + '</span>'))
  }
  
  $('body').append($('<span> (a=' + a + '; c=' + c + '; m=' + m  + ')</span>'))
}


function shuffle() { 
  do_shuffle($('#len').val());
}

shuffle()