javascript中如何根据固定字符集生成随机数

Question

我正在根据固定字符集生成数字。

function generator()
{
     var text = "";
     var char_list = "LEDGJR", number_list = "0123456789";
     for(var i=0; i < 2; i++ )
     {  
          text += char_list.charAt(Math.floor(Math.random() * char_list.length));
     }

     for(var j=0; j < 2; j++ )
     {  
          text += number_list.charAt(Math.floor(Math.random() *             
                              number_list.length));
     }

     return text;
}

结果： RE39、JE12 等...

一旦完成与上述序列相关的所有排列，则生成器应生成字符串 RE391，JE125 表示在完整数字上再加一个数字。

如何获取序列的排列数？

Answer 1

为简单起见，考虑以下情况：

chars = "AB"
nums = "123";

我们想要生成一个由两个字符和两个数字组成的 4 位数字序列。

我们定义这些变量

rows = [chars, chars, nums, nums]
rowSizes = rows.map(row => row.length) // [2, 2, 3, 3]

很容易看出所有可能排列的集合大小等于：

spaceSize = rowSizes.reduce((m, n) => m * n, 1) // 2*2*3*3 = 36

并且我们定义了两组效用函数，稍后我会详细解释它们的用法。

decodeIndex() 这给了我们独特性

function euclideanDivision(a, b) {
  const remainder = a % b;
  const quotient =  (a - remainder) / b;
  return [quotient, remainder]
}

function decodeIndex(index, rowSizes) {
  const rowIndexes = []
  let dividend = index
  for (let i = 0; i < rowSizes.length; i++) {
    const [quotient, remainder] = euclideanDivision(dividend, rowSizes[i])
    rowIndexes[i] = remainder
    dividend = quotient
  }
  return rowIndexes
}

getNextIndex() 这给了我们 pseudo-randomness

function isPrime(n) {
  if (n <= 1) return false;
  if (n <= 3) return true;

  if (n % 2 == 0 || n % 3 == 0) return false;

  for (let i = 5; i * i <= n; i = i + 6) {
    if (n % i == 0 || n % (i + 2) == 0) return false;
  }
  return true;
}

function findNextPrime(n) {
  if (n <= 1) return 2;
  let prime = n;

  while (true) {
    prime++;
    if (isPrime(prime)) return prime;
  }
}

function getIndexGeneratorParams(spaceSize) {
  const N = spaceSize;
  const Q = findNextPrime(Math.floor(2 * N / (1 + Math.sqrt(5))))
  const firstIndex = Math.floor(Math.random() * spaceSize);
  
  return [firstIndex, N, Q]
}

function getNextIndex(prevIndex, N, Q) {
  return (prevIndex + Q) % N
}

唯一性

如上所述，spaceSize 是所有可能排列的数量，因此 range(0, spaceSize) 中的每个 index 唯一映射到一个排列。 decodeIndex 有助于此映射，您可以通过以下方式获得 index 的相应排列：

function getSequenceAtIndex(index) {
  const tuple = decodeIndex(index, rowSizes)
  return rows.map((row, i) => row[tuple[i]]).join('')
}

Pseudo-Randomness

（归功于 this question。我只是将该代码移植到 JS 中。）

我们通过轮询“全循环迭代器”得到 pseudo-randomness^†。思路很简单：

将索引 0..35 布局在一个圆圈中，将上限表示为 N=36
决定一个步长，表示为Q（本例中为Q=23）由这个公式给出^‡
Q = findNextPrime(Math.floor(2 * N / (1 + Math.sqrt(5))))
随机决定一个起点，例如数 5
开始从 prevIndex 生成看似随机的 nextIndex，由
nextIndex = (prevIndex + Q) % N

因此，如果我们将 5 放入，我们将得到 (5 + 23) % 36 == 28。将 28 放入我们得到 (28 + 23) % 36 == 15.

这个过程会遍历一个圈中的每个数字（在圈中的点之间来回跳转），每个数字只取一次，不重复。当我们回到起点 5 时，我们知道我们已经到达终点。

_{†：我不确定这个词，只是引用this answer}
_{‡：这个公式只给出了一个很好的步长，会让事情看起来更“随机”，对 Q 的唯一要求是它必须与 N} 互质

完整解决方案

现在让我们把所有的部分放在一起。运行查看结果的片段。

我还在每个日志前添加了一个计数器。对于 char_list="LEDGJR", number_list="0123456789" 的情况，4 位序列的 spaceSize 应该是 6*6*10*10 = 3600

您会在 3601 处观察到对数碰撞到 5 位序列

function euclideanDivision(a, b) {
  const remainder = a % b;
  const quotient = (a - remainder) / b;
  return [quotient, remainder];
}

function decodeIndex(index, rowSizes) {
  const rowIndexes = [];
  let divident = index;
  for (let i = 0; i < rowSizes.length; i++) {
    const [quotient, remainder] = euclideanDivision(divident, rowSizes[i]);
    rowIndexes[i] = remainder;
    divident = quotient;
  }
  return rowIndexes;
}

function isPrime(n) {
  if (n <= 1) return false;
  if (n <= 3) return true;

  if (n % 2 == 0 || n % 3 == 0) return false;

  for (let i = 5; i * i <= n; i = i + 6) {
    if (n % i == 0 || n % (i + 2) == 0) return false;
  }
  return true;
}

function findNextPrime(n) {
  if (n <= 1) return 2;
  let prime = n;

  while (true) {
    prime++;
    if (isPrime(prime)) return prime;
  }
}

function getIndexGeneratorParams(spaceSize) {
  const N = spaceSize;
  const Q = findNextPrime(Math.floor((2 * N) / (1 + Math.sqrt(5))));
  const firstIndex = Math.floor(Math.random() * spaceSize);

  return [firstIndex, N, Q];
}

function getNextIndex(prevIndex, N, Q) {
  return (prevIndex + Q) % N;
}

function generatorFactory(rows) {
  const rowSizes = rows.map((row) => row.length);

  function getSequenceAtIndex(index) {
    const tuple = decodeIndex(index, rowSizes);
    return rows.map((row, i) => row[tuple[i]]).join("");
  }

  const spaceSize = rowSizes.reduce((m, n) => m * n, 1);

  const [firstIndex, N, Q] = getIndexGeneratorParams(spaceSize);

  let currentIndex = firstIndex;
  let exhausted = false;

  function generator() {
    if (exhausted) return null;
    const sequence = getSequenceAtIndex(currentIndex);
    currentIndex = getNextIndex(currentIndex, N, Q);
    if (currentIndex === firstIndex) exhausted = true;
    return sequence;
  }

  return generator;
}

function getRows(chars, nums, rowsOfChars, rowsOfNums) {
  const rows = [];
  while (rowsOfChars--) {
    rows.push(chars);
  }
  while (rowsOfNums--) {
    rows.push(nums);
  }
  return rows;
}

function autoRenewGeneratorFactory(chars, nums, initRowsOfChars, initRowsOfNums) {
  let realGenerator;
  let currentRowOfNums = initRowsOfNums;

  function createRealGenerator() {
    const rows = getRows(chars, nums, initRowsOfChars, currentRowOfNums);
    const generator = generatorFactory(rows);
    currentRowOfNums++;
    return generator;
  }

  realGenerator = createRealGenerator();

  function proxyGenerator() {
    const sequence = realGenerator();
    if (sequence === null) {
      realGenerator = createRealGenerator();
      return realGenerator();
    } else {
      return sequence;
    }
  }

  return proxyGenerator;
}

function main() {
  const char_list = "LEDGJR"
  const number_list = "0123456789";
  const generator = autoRenewGeneratorFactory(char_list, number_list, 2, 2);
  let couter = 0
  setInterval(() => {
    console.log(++couter, generator())
  }, 10);
}

main();

javascript中如何根据固定字符集生成随机数

How to generate a random number based on fixed character set in javascript

javascript

random

sequence

唯一性

Pseudo-Randomness

完整解决方案