algorithm - 没有重复结果的随机生成器

Question

我需要把从 low 到 high 的数字随机放入一个数组中。

例如给定:low = 10, high = 15 这样的结果 [ 12, 13, 10, 14, 11] 是好的。

这是一个简单的算法:从低到高迭代并尝试填充数组上的空槽。

const low = 1000
const high = 1010

const diff = high - low
const arr = new Array(diff)

for (var i = low; i < high; i++) {
  let success = false
  while(!success) {
    const index = Math.floor(Math.random() * diff)
    if (arr[index] === undefined) {
      arr[index] = i
      success = true
    }
    console.log(`${index} was ${success ? 'available' : 'taken'}`)
  }
}

console.log(arr)

问题是:最后大部分元素都被填满了，就很难在数组中找到未被占用的槽位。

我的问题是:是否有一种算法可以不断生成唯一的新数字，直到所有数字都被消耗完？

另一种思考方式是一种以最有效和最快的方式对数组进行混洗的算法。

Answer 1

不是生成“随机”数字，而是生成数字列表并使用类似 Fisher-Yates Shuffle 的方式“随机”打乱它。 :

function getRandomArray(min, max) {
  return shuffle([...Array(max - min).keys()].map(i => i + min));
}

function shuffle(array) {
  var m = array.length, t, i;

  while (m) {

    i = Math.floor(Math.random() * m--);

    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }

  return array;
}

var randomArr = getRandomArray(10, 15);
console.log(randomArr);