Javascript random ordering with seed

问题:

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?

回答1:

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()));

回答2:

SeededShuffle

Works on node and browser.

回答3:

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.

回答4:

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