Javascript random ordering with seed

Question

I want to randomly shuffle a list of 4 items but with a seed so that so long as you have the same seed the you will get the same order of items.

["a", "b", "c", "d"]

I figure I can get the seed with Math.random, I don't need something very exact. How do I sort according to the seed?

Answer 1

You can achieve this with a slight modification to Mike Bostock's implementation of the Fisher–Yates algorithm*:

function shuffle(array, seed) {                // <-- ADDED ARGUMENT
  var m = array.length, t, i;

  // While there remain elements to shuffle…
  while (m) {

    // Pick a remaining element…
    i = Math.floor(random(seed) * m--);        // <-- MODIFIED LINE

    // And swap it with the current element.
    t = array[m];
    array[m] = array[i];
    array[i] = t;
    ++seed                                     // <-- ADDED LINE
  }

  return array;
}

function random(seed) {
  var x = Math.sin(seed++) * 10000; 
  return x - Math.floor(x);
}

*The random function is taken from this SO answer. It is a hack and not entirely random and most importantly not cryptographically secure! Here's a histogram of samples (also in the comments of that response, takes a while to run). Conclusively, you should only use this when these things don't really matter. Alternatively, substitute the random function with a better seedable random number generator.

Answer 2

Shuffling an array with a seed is two separate problems:

1. Seeding the random number generator used to shuffle the array
2. Using the seeded random number generator to shuffle the array

For seeding the random number generator, see this fantastic answer in the thread Seeding the random number generator in Javascript.

For shuffling an array, see the Fisher-Yates shuffle in How can I shuffle an array?.

Here's some code that conveniently wraps the two together. It's up to you to copy and paste a couple of small functions from this answer. I'd rather not dupe the code in case it changes, and this lets you plug and play whatever seeded random functions you want.

// TODO: copy and paste mulberry32 and xmur3 from
//       https://stackoverflow.com/a/47593316/6243352

const seededRandom = ({rng = null, seed = "apples"} = {}) => {
  rng = rng || mulberry32(xmur3(seed)());
  
  const rnd = (lo, hi, defaultHi=1) => {
    if (hi === undefined) {
      hi = lo === undefined ? defaultHi : lo;
      lo = 0;
    }
    
    return rng() * (hi - lo) + lo;
  };

  const rndInt = (lo, hi) => Math.floor(rnd(lo, hi, 2));
  
  const shuffle = a => {
    for (let i = a.length - 1; i > 0; i--) {
      const j = rndInt(i + 1);
      const x = a[i];
      a[i] = a[j];
      a[j] = x;
    }
  };
  
  return {rnd, rndInt, shuffle};
};

module.exports = seededRandom;

You can use it like:

const seededRandom = require("./seeded-random");

const {
  rnd, rndInt, shuffle
} = seededRandom({seed: "optional seed string"});
const a = [...Array(5)].map((_, i) => i);
shuffle(a);

// comments assume mulberry32 and xmur3 from
// https://stackoverflow.com/a/47593316/6243352
console.log(a); // => always [ 2, 0, 3, 1, 4 ]
console.log(rnd()); // => always 0.8192486129701138
console.log(rndInt(42)); // => always 41

Answer 3

You can create random numbers to do the sorting using the XOR Shift method. Example. Then just replace Math.random() in your old code with new Xor128(seed).make(3)[2] / 4294967296 * 2

Answer 4

jsFiddle Demo

You would need to seed a random value for each value in the array as far as I can tell. In that regards, you would probably want to do something like this:

for( var i = 0; i < length; i++ ){
    seed.push(Math.random());
}

Where you are insuring that length is the same length that the seed is for. This would be 4 for your simple example. Once that was done, you could pass the seed into your shuffle (or sort) function to ensure that the same results were obtained. The shuffle would need to use it in a loop as well

    var randomIndex = parseInt(seed[i] * (len - i));

So here is what it all breaks down into

The seed function which will store the array of seeds

var seeder = function(){
 var seed = [];
 return {
  set:function(length){
    for( var i = 0; i < length; i++ ){
        seed.push(Math.random());
    }
    return seed;
  },
  get: function(){
   return seed;
  },
  clear: function(){
   seed = []; 
  }
 };
}

A pretty basic shuffle

function randomShuffle(ar,seed){
var numbers = [];
for( var a = 0, max = ar.length; a < max; a++){
    numbers.push(a);
}
var shuffled = [];
for( var i = 0, len = ar.length; i < len; i++ ){
    var r = parseInt(seed[i] * (len - i));
    shuffled.push(ar[numbers[r]]);
    numbers.splice(r,1);
}
return shuffled;
}

Being used

var arr = ["a", "b", "c", "d"];
var seed = seeder();
seed.set(arr.length);
console.log(randomShuffle(arr,seed.get()));
console.log(randomShuffle(arr,seed.get()));
console.log(randomShuffle(arr,seed.get()));