Generate random & unique 4 digit codes without brute force

Question

I'm building an app and in one of my functions I need to generate random & unique 4 digit codes. Obviously there is a finite range from 0000 to 9999 but each day the entire list will be wiped and each day I will not need more than the available amount of codes which means it's possible to have unique codes for each day. Realistically I will probably only need a few hundred codes a day.

The way I've coded it for now is the simple brute force way which would be to generate a random 4 digit number, check if the number exists in an array and if it does, generate another number while if it doesn't, return the generated number.

Since it's 4 digits, the runtime isn't anything too crazy and I'm mostly generating a few hundred codes a day so there won't be some scenario where I've generated 9999 codes and I keep randomly generating numbers to find the last remaining one.

It would also be fine to have letters in there as well instead of just numbers if it would make the problem easier.

Other than my brute force method, what would be a more efficient way of doing this?

Thank you!

Answer 1

Since you have a constrained number of values that will easily fit in memory, the simplest way I know of is to create a list of the possible values and select one randomly, then remove it from the list so it can't be selected again. This will never have a collision with a previously used number:

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

This works by doing the following:

1. Generate an array of all possible values.
2. When you need a value, select one from the array with a random index.
3. After selecting the value, remove it from the array.
4. Return the selected value.
5. Items are never repeated because they are removed from the array when used.
6. There are no collisions with used values because you're always just selecting a random value from the remaining unused values.
7. This relies on the fact that an array of integers is pretty well optimized in Javascript so doing a .splice() on a 10,000 element array is still pretty fast (as it can probably just be memmove instructions).

FYI, this could be made more memory efficient by using a typed array since your numbers can be represented in 16-bit values (instead of the default 64 bits for doubles). But, you'd have to implement your own version of .splice() and keep track of the length yourself since typed arrays don't have these capabilities built in.

For even larger problems like this where memory usage becomes a problem, I've used a BitArray to keep track of previous usage of values.

---

Here's a class implementation of the same functionality:

class Randoms {
    constructor(numValues) {
        this.values = new Array(numValues);
        for (let i = 0; i < this.values.length; i++) {
            this.values[i] = i;
        }
    }
    getRandomValue() {
        if (!this.values.length) {
            throw new Error("no more random values");
        }
        const i = Math.floor(Math.random() * this.values.length);
        const returnVal = this.values[i];
        this.values.splice(i, 1);
        return returnVal;
    }
}

const rands = new Randoms(10000);
console.log(rands.getRandomValue());
console.log(rands.getRandomValue());
console.log(rands.getRandomValue());
console.log(rands.getRandomValue());

Answer 2

Knuth's multiplicative method looks to work pretty well: it'll map numbers 0 to 9999 to a random-looking other number 0 to 9999, with no overlap:

const hash = i => i*2654435761 % (10000);
const s = new Set();
for (let i = 0; i < 10000; i++) {
  const n = hash(i);
  if (s.has(n)) { console.log(i, n); break; }
  s.add(n);
}

To implement it, simply keep track of an index that gets incremented each time a new one is generated:

const hash = i => i*2654435761 % (10000);
let i = 1;
console.log(
  hash(i++),
  hash(i++),
  hash(i++),
  hash(i++),
  hash(i++),
);

These results aren't actually random, but they probably do the job well enough for most purposes.

Answer 3

Disclaimer:

This is copy-paste from my answer to another question here. The code was in turn ported from yet another question here.

Utilities:

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
}

Usage

// Each day you bootstrap to get a tuple of these parameters and persist them throughout the day. 

const [firstIndex, N, Q] = getIndexGeneratorParams(10000)

// need to keep track of previous index generated. 
// it’s a seed to generate next one. 
let prevIndex = firstIndex

// calling this function gives you the unique code
function getHashCode() {
  prevIndex = getNextIndex(prevIndex, N, Q)
  return prevIndex.toString().padStart(4, "0")
}

console.log(getHashCode());

Explanation

For simplicity let’s say you want generate non-repeat numbers from 0 to 35 in random order. 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}

Answer 4

This problem is so small I think a simple solution is best. Build an ordered array of the 10k possible values & permute it at the start of each day. Give the k'th value to the k'th request that day.

It avoids the possible problem with your solution of having multiple collisions.