在JavaScript中生成两个限定范围内不重复的随机数字。

Question

除了数组切片之外，还有没有其他方法可以生成在两个数字之间的随机数，而且不会重复直到这两个数字之间的所有数字都被生成？洗牌技术或除了切片之外的任何其他数组方法都将非常有帮助。

- Ronophobia

---

Fisher-Yates 洗牌算法：https://dev59.com/IXE95IYBdhLWcg3wHqMVFisher-Yates 洗牌算法是一种用于随机排序数组的算法。它遍历数组中的每个元素，然后将该元素与随机位置上的另一个元素进行交换。重复这个过程直到数组被完全打乱。以下是使用 JavaScript 实现 Fisher-Yates 洗牌算法的代码：function shuffle(array) { var currentIndex = array.length, temporaryValue, randomIndex; // While there remain elements to shuffle... while (0 !== currentIndex) { // Pick a remaining element... randomIndex = Math.floor(Math.random() * currentIndex); currentIndex -= 1; // And swap it with the current element. temporaryValue = array[currentIndex]; array[currentIndex] = array[randomIndex]; array[randomIndex] = temporaryValue; } return array; }您可以将您想要随机化的数组传递给 shuffle 函数，并返回一个新的已随机排序的数组。 - thefrontender

Answer 1

首先，我们使用FisherYates实现（感谢@ChristopheD）来随机化JavaScript数组，并扩展了数组原型以使洗牌函数可用。

function arrayShuffle () {
   var i = this.length, j, temp;
   if ( i === 0 ) return false;
   while ( --i ) {
      j = Math.floor( Math.random() * ( i + 1 ) );
      temp = this[i];
      this[i] = this[j]; 
      this[j] = temp;
   }
}

Array.prototype.shuffle =arrayShuffle;

var numbers = new Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
numbers.shuffle();

现在使用pop方法，我们从种子中获取一个数字，直到它为空。

numbers.pop(); //returns a number

为了确保我们拥有一个由 start 和 end 范围内的数字填充的数组，我们使用简单的循环来创建我们的种子。

var start = 1;
var end = 5;
var numbers = new Array();
for (var i = start; i <= end; i++) {
    numbers.push(i);
}

这是一个在jsfiddle上的示例。

更新：使用Fisher-Yates算法使洗牌更有效。

- MatthiasLaug

---

这是一个糟糕的（非均匀）洗牌算法。要看出它不能是均匀洗牌，只需考虑有N ** N个等可能的洗牌，而N个元素的排列数为N！，通常情况下N ** N不是N！的精确倍数。 - 6502

这不是正确的洗牌方式。查找 Fisher-Yates 洗牌算法。你只能在列表后面随机每个成员。这样可以得到 n! 种可能的排列方式，这是确保每个元素恰好出现一次的正确数量。 - Patashu

@MatthaisLaug，你的洗牌算法是错误的。也就是说，它是有偏差的。也就是说，它并没有平等地选择所有的洗牌方式。这就是我们抱怨的原因，因为缺乏正确性是非常糟糕的 :) - Patashu

但是，如果我想在两个数字之间（包括这两个数字）找到一个数字，并将数组填满这些数字，那么对于数组的每个连续调用 Fisher-Yates 洗牌函数，它是否会返回数组内容的不同组合？就像所有可能的组合都会在重复之前得到满足一样？因为这正是我正在寻找的 :/ - Ronophobia

Fisher-Yates算法是一种用于生成有限集合的随机排列的算法，简单来说，就是用于随机洗牌集合。但有时候，在所有排列都出现之前，可能会再次得到相同的排列。如果要避免这种情况，需要向shuffle方法提供一个数组的数组，以检查新的洗牌数组是否已被使用过。 - MatthiasLaug

Answer 2

当我处理较小的数组时，通常会通过随机排序数组来处理：

yourArray.sort(function() { return 0.5 - Math.random() });

- Max Fahl

Answer 3

试试这个 http://jsbin.com/imukuh/1/edit：

function randRange(min, max) {
  var result = [];
  for (var i=min; i<=max; i++) result.push(i);
  return result.map(function(v){ return [Math.random(), v] })
    .sort().map(function(v){ return v[1] });
}

console.log(randRange(1,5));
// [4, 3, 1, 5, 2]
// [3, 5, 2, 4, 1]
// [1, 5, 2, 3, 4]
// [3, 2, 5, 1, 4]
// ...

- elclanrs