How to use memoization to generate non-repeating random numbers?

Question

I'd like to use a self-written function to generate non-repeating random keys for HTML elements.

The issue is that the cache gets lost at each function call.

This is my code so far:

function generateRandomKey(cache = []) {
  const newRandomKey = Number(Math.random().toFixed(2));
  if (cache.includes(newRandomKey)) return generateRandomKey(cache);
  cache.push(newRandomKey);
  return newRandomKey;
}

I could declare cache out of the function scope, which would be available globally as I would like the cache to be, but I'm afraid this would be bad practice.

I've thought of using memoization, something like this:

const memoizedRandomKey = (cache = []) => {
  return (generateRandomKey) => {
    const key = generateRandomKey();
    if (cache.includes(key) {
      return memoizedRandomKey(cache)
    }
    else {
      cache.push(key)
      return key
    }
  }
}

However the cache also keeps getting overwritten.

I am not sure what I am doing wrong or if memoization would even be useful in this case.

Which approach would you recommend? Where is the flaw in my logical thinking?

Thank you.

Answer 1

don't use random keys

Each time you reach into the same random space, there's a potential that you receive a non-unique value. To check whether you have already seen a particular value, you would need some sort of cache.

don't use a cache

As the cache fills up, it's harder and harder to find a unique value that hasn't be used.

don't use splice

Using .splice resizes the array each time a random is generated. This is a very costly operation.

keep it simple

This sequential ID generator guarantees the IDs will be unique, without any need for collision detection, caching, preallocation, or other expensive computations. For use with generated HTML elements, this is sufficient -

function createGenerator(init = 0) {
  return () => (init++).toString(16).padStart(2, "0")
}

const foo = createGenerator(1000)
const bar = createGenerator()

console.log(foo(), foo()) // 3e8 3e9
console.log(bar(), bar()) // 00 01

console.log(foo(), foo()) // 3ea 3eb
console.log(bar(), bar()) // 02 03

preallocated, random order identifiers

If the identifiers are known or computed ahead of time, let's explore an alternative -

const t = popRandom(["a", "b", "c", "d", "e", "f"])

console.log(t(),t(),t()) // d c a
console.log(t(),t(),t()) // b e f
console.log(t())         // Error: no more values

Starting with the input array and n = keys.length, random r can be any value 0 up to (excluding) n. Let's say r = 3 for the first iteration -

["a", "b", "c", "d", "e", "f"]
                 ^ r = 3

"d" will be the first return value, then swap keys[r] with end of the array keys[n - 1], resulting in -

["a", "b", "c", "f", "e", "d"]

In the next iteration n = 5 so the only valid random elements are a, b, c, f, e -

["a", "b", "c", "f", "e", "d"]
  ^    ^    ^    ^    ^
                      n = 5

Once n = 0, there are no more values and alert the caller. Now we implement it -

function popRandom(keys) {
  let n = keys.length
  let r, q
  return () => {
    if (n == 0) throw Error("no more values")
    r = Math.random() * n >> 0;
    q = keys[r]
    keys[r] = keys[n - 1]
    keys[n - 1] = q
    n -= 1
    return q
  }
}

const keys = ["a", "b", "c", "d", "e", "f"]
const t = popRandom(keys)

console.log(t(),t(),t()) // e d a
console.log(t(),t(),t()) // c f b
console.log(keys) // keys are shuffled
console.log(t()) // error no more values

shuffled output

once popRandom has exhausted all possible values, the input keys will be shuffled. See Fisher-Yates shuffle for more info.

immutable keys

If you don't want to mutate the input keys, simply copy them at input -

const t = popRandom([...myKeys]) // copy 
// t(); t(); t(); ...