无需暴力破解即可生成随机且唯一的 4 位代码

Question

我正在构建一个应用程序，在我的一个函数中，我需要生成随机且唯一的 4 位数代码。显然，从 0000 到 9999 的范围是有限的，但每天整个列表都会被擦除，每天我都不需要超过可用数量的代码，这意味着每天都有可能有唯一的代码。实际上，我每天可能只需要几百个代码。

我现在编码的方式是简单的暴力方式，即生成一个随机的 4 位数字，检查该数字是否存在于数组中，如果存在，则生成另一个数字，如果不存在，则返回生成的数字。

由于它是 4 位数字，所以运行时间并不算太疯狂，而且我每天主要生成几百个代码，因此不会出现生成 9999 个代码并且我不断随机生成数字来查找最后一个代码的情况剩下一张。

如果可以让问题变得更容易的话，也可以在其中包含字母而不仅仅是数字。

除了我的蛮力方法之外，还有什么更有效的方法呢？

谢谢你！

Answer 1

由于内存中的值数量有限，因此我知道的最简单的方法是创建一个可能值的列表并随机选择一个，然后将其从列表中删除，这样就无法再次选择它。这永远不会与以前使用的数字发生冲突：

function initValues(numValues) {
    const values = new Array(numValues);
    // fill the array with each value
    for (let i = 0; i < values.length; i++) {
        values[i] = i;
    }
    return values;
}

function getValue(array) {
    if (!array.length) {
        throw new Error("array is empty, no more random values");
    }
    const i = Math.floor(Math.random() * array.length);
    const returnVal = array[i];
    array.splice(i, 1);
    return returnVal;
}

// sample code to use it
const rands = initValues(10000);
console.log(getValue(rands));
console.log(getValue(rands));
console.log(getValue(rands));
console.log(getValue(rands));

这是通过执行以下操作来实现的：

1. 生成所有可能值的数组。
2. 当您需要一个值时，请从具有随机索引的数组中选择一个值。
3. 选择值后，将其从数组中删除。
4. 返回选定的值。
5. 项目永远不会重复，因为它们在使用时会从数组中删除。
6. 与已使用的值不会发生冲突，因为您始终只是从剩余的未使用值中选择一个随机值。
7. 这依赖于这样一个事实：整数数组在 Javascript 中得到了很好的优化，因此.splice()在 10,000 个元素数组上执行 a 仍然相当快（因为它可能只是 memmove 指令）。

仅供参考，通过使用类型化数组可以提高内存效率，因为您的数字可以用 16 位值表示（而不是默认的双精度 64 位）。但是，您必须实现自己的版本.splice()并自己跟踪长度，因为类型化数组没有内置这些​​功能。

对于像这样内存使用成为问题的更大问题，我使用 BitArray 来跟踪值的先前使用情况。

这是相同功能的类实现：

function initValues(numValues) {
    const values = new Array(numValues);
    // fill the array with each value
    for (let i = 0; i < values.length; i++) {
        values[i] = i;
    }
    return values;
}

function getValue(array) {
    if (!array.length) {
        throw new Error("array is empty, no more random values");
    }
    const i = Math.floor(Math.random() * array.length);
    const returnVal = array[i];
    array.splice(i, 1);
    return returnVal;
}

// sample code to use it
const rands = initValues(10000);
console.log(getValue(rands));
console.log(getValue(rands));
console.log(getValue(rands));
console.log(getValue(rands));