javascript - 带有种子的Javascript随机排序

Question

我想随机打乱一个包含 4 个项目的列表，但有一个种子，这样只要你有相同的种子，你就会得到相同的项目顺序。

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

我想我可以用 Math.random 获得种子，我不需要非常精确的东西。我如何根据种子排序？

Answer 1

您可以通过对Mike Bostock 的Fisher–Yates 算法*的实现稍作修改来实现这一点：

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

*random函数取自这个 SO answer。这是一种黑客攻击，不是完全随机的，最重要的是不是加密安全的！这是样本的直方图（也在该响应的评论中，需要一段时间才能运行）。最后，你应该只在这些事情并不重要时才使用它。或者，random用更好的可种子随机数生成器替换该函数。

Answer 2

用种子对数组进行洗牌是两个独立的问题：

1. 播种用于打乱数组的随机数生成器
2. 使用种子随机数生成器对数组进行洗牌

要播种随机数生成器，请参阅线程在 Javascript 中播种随机数生成器中的这个奇妙答案。

要对数组进行洗牌，请参阅如何洗牌中的Fisher-Yates洗牌？.

这是一些方便地将两者包装在一起的代码。您可以从这个答案中复制和粘贴几个小功能。我宁愿不要复制代码以防它发生变化，这可以让你即插即用你想要的任何种子随机函数。

// 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;

你可以像这样使用它：

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

您可以使用 XOR Shift 方法创建随机数来进行排序。 例子。 然后只需将Math.random()旧代码替换为new Xor128(seed).make(3)[2] / 4294967296 * 2

Answer 4

jsFiddle Demo

据我所知，您需要为数组中的每个值播种一个随机值。在这方面，你可能想要做这样的事情：

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

您要确保length与种子的长度相同。对于您的简单示例，这将是 4。完成后，您可以将种子传递到您的 shuffle（或排序）函数中，以确保获得相同的结果。洗牌也需要在循环中使用它

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

所以这就是它的全部内容

将存储种子数组的种子函数

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 = []; 
  }
 };
}

一个非常基本的洗牌

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;
}

正在使用

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