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

Answer 2

The reason your memoizedRandomKey function doesn't work is that you're calling the wrong function in the recursive case. You should be calling the function that it returns, but that function is unnamed, so you'd have to name it. We could do it like this:

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

But I think this could be cleaned up a bit. So I might try something like this:

const generateRandomKey = () => Math .random() .toFixed (2) .slice (2)

const makeRandomizer = (generator, cache = []) => (key = generator ()) =>
  key in cache
    ? makeRandomizer (generator) ()
    : (cache .push (key), key)


const randomId = makeRandomizer (generateRandomKey)

console .log (Array .from ({length: 50}, () => randomId ()))

.as-console-wrapper {max-height: 100% !important; top: 0}

Still, as others have pointed out, this can run into problems of repeatedly checking as your cache fills up. An alternative would be to generate all the keys on start, shuffle them, then keep the current index in your closure. This is easy enough to do when you are limiting yourself to just 100 possibilities, but will get to be a problem for a larger space of potential ids.

For larger cases, you would have to decide what you mean by random, and how much a problem of id collisions would be. If it's just that they should not seem predictable to casual eyes, then you might try a Linear Congruential Generator, which is easy to calculate, and by starting with a random seed, will look different from run to run. Remember that while you can make the period as long as you like, but it will be periodic. If you need something more random, then look at Crypto.getRandom, but remember that, as unlikely as collisions are, they can happen.

Answer 3

With your code you can make 100 keys (0.00 to 0.99). As the cache gets large, the collisions will occur more frequently and you will have a lot of recursive calls - possibly leading to issues like stack overflow. A better solution might be to create all the keys first, then randomly select/remove them as needed.

I work mostly in C++ and C#, so I naturally prefer using classes. (Although it seems JS programmers don't use them too much?). So here's a static class. It creates the 100 keys, then removes/returns them until the list is empty.

class RandomKey {
    static keys = Array.apply(null, Array(100)).map((x, i) => (i / 100).toFixed(2));

    static generate() {
        if (RandomKey.keys.length == 0) {
            throw new Error("No more keys.");
        }
        const index = Math.floor(RandomKey.keys.length * Math.random());
        const selectedKey = RandomKey.keys[index];
        RandomKey.keys.splice(index, 1);
        return selectedKey;
    }
}

// Test
for (let i = 0; i < 101; i++) {
    console.log(RandomKey.generate());
}

Answer 4

I think you're on the right track. You typically want your cache to be part of the closure instead of passing it in as an argument. Maybe something like this.

const generateRandomKey = () => Math.random().toFixed(10)

function makeKeyGenerator() {
  const cache = {};
  return function () {
    let key = generateRandomKey();
    // if the key is in the cache get a new key
    while (key in cache) {
      key = generateRandomKey();
    }
    cache[key] = true;
    console.log(cache);
    return key;
  };
}

const getKey = makeKeyGenerator();

const key = getKey();

Note that you're going to run out of keys pretty quickly with toFixed(2). And if that happens, the while loop is going to make you have a bad day.