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)

问题是：在大部分元素都被填满的地方，很难在数组中找到一个未被占用的槽。

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

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

标签： algorithmrandom

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