How To Generate A Random Number Based On Fixed Character Set In Javascript

I'm generating a number based on a fixed character set. function generator() { var text = ''; var char_list = 'LEDGJR', number_list = '0123456789'; for(var i=0; i &l

Solution 1:

For simplicity consider the case where:

chars = "AB"nums = "123";

and we want to generate a 4-digit sequence of two chars and two numbers.

We define these variables

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

It’s easy to see the set size of all possible permuations equals:

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

And we define two set of utility functions, usage of which I'll explain in detail later.

1. decodeIndex() which gives us uniqueness

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

functiondecodeIndex(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
}

2. getNextIndex() which gives us pseudo-randomness

functionisPrime(n) {
  if (n <= 1) returnfalse;
  if (n <= 3) returntrue;

  if (n % 2 == 0 || n % 3 == 0) returnfalse;

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

functionfindNextPrime(n) {
  if (n <= 1) return2;
  let prime = n;

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

functiongetIndexGeneratorParams(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]
}

functiongetNextIndex(prevIndex, N, Q) {
  return (prevIndex + Q) % N
}

Uniqueness

Like mentioned above, spaceSize is the number of all possible permutations, thus each index in range(0, spaceSize) uniquely maps to one permutation. decodeIndex helps with this mapping, you can get the corresponding permutation to an index by:

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

Pseudo-Randomness

(Credit to this question. I just port that code into JS.)

We get pseudo-randomness by polling a "full cycle iterator". The idea is simple:

1. have the indexes 0..35 layout in a circle, denote upperbound as N=36
2. decide a step size, denoted as Q (Q=23 in this case) given by this formula Q = findNextPrime(Math.floor(2 * N / (1 + Math.sqrt(5))))
3. randomly decide a starting point, e.g. number 5
4. start generating seemingly random nextIndex from prevIndex, by nextIndex = (prevIndex + Q) % N

So if we put 5 in we get (5 + 23) % 36 == 28. Put 28 in we get (28 + 23) % 36 == 15.

This process will go through every number in circle (jump back and forth among points on the circle), it will pick each number only once, without repeating. When we get back to our starting point 5, we know we've reach the end.

_{†: I'm not sure about this term, just quoting from this answer‡: This formula only gives a nice step size that will make things look more "random", the only requirement for Q is it must be coprime to N}

Full Solution

Now let's put all the pieces together. Run the snippet to see result.

I've also includes the a counter before each log. For your case with char_list="LEDGJR", number_list="0123456789", the spaceSize for 4-digit sequence should be 6*6*10*10 = 3600

You'll observe the log bump to 5-digit sequence at 3601 😉

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

functiondecodeIndex(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;
}

functionisPrime(n) {
  if (n <= 1) returnfalse;
  if (n <= 3) returntrue;

  if (n % 2 == 0 || n % 3 == 0) returnfalse;

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

functionfindNextPrime(n) {
  if (n <= 1) return2;
  let prime = n;

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

functiongetIndexGeneratorParams(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];
}

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

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

  functiongetSequenceAtIndex(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;

  functiongenerator() {
    if (exhausted) returnnull;
    const sequence = getSequenceAtIndex(currentIndex);
    currentIndex = getNextIndex(currentIndex, N, Q);
    if (currentIndex === firstIndex) exhausted = true;
    return sequence;
  }

  return generator;
}

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

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

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

  realGenerator = createRealGenerator();

  functionproxyGenerator() {
    const sequence = realGenerator();
    if (sequence === null) {
      realGenerator = createRealGenerator();
      returnrealGenerator();
    } else {
      return sequence;
    }
  }

  return proxyGenerator;
}

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

main();