How to randomize a generator output in JavaScript?

Question

Let's pretend I have a generator which eventually stops

function* letters () {
  let offset = 0
  while (offset < 26)
    yield String.fromCharCode(65 + offset++)
}

console.log(Array.from(letters()))
// => [ "A", "B", "C", ..., "X", "Y", "Z" ]

Using that generator as an input, I want to create another generator, but for this one I would like the values to come out in a randomized order

function* randomizeGen (gen) {
  // ...
}

Array.from(randomizeGen(letters()))
// => [ "X", "T", "L", "P", "A", ..., "G", "S", "B" ] (all 26 letters)

The new generator should be lazy, like the first one, but I cannot figure out how to write it in a smart way

function shuffleArray (arr) {
  // return shuffled array
}

function* randomizeGen (gen) {
   const all = Array.from(gen) // help!
   for (const one of shuffleArray(all))
     yield one
}

This would work, but it does so by completely exhausting gen first. In reality, my initial generator outputs millions of values, so I don't think collecting them all in an array first is a good idea. The whole point of using a generator is that I can process the values one at a time

I honestly have no idea how to randomize the generator output but keep it lazy at the same time. Can someone please help?

Answer 1

You can't, by definition. A generator produces a single value in a specific order every time it is invoked. So if you want some other value rather than the next one in line, you will have to consume multiple values from the generator, and then select one to return. Which is eager evaluation rather then lazy.

---

However you could simulate the intended behaviour like this. It will remain lazy for about 50% of the time. So its kinda-lazy.

Note that this is far from an actually random order. The first half of the elements in the generator will each have a 50% chance of being put in the right order (and 50% chance of being put in the cache). While the second half of elements will have a 2/n chance of being put in the right order (where n is the current number of elements in the cache, aka n will go from N/2 to 0 (where N is the number of elements in the generator in total)).

TL:DR the first half of the "random" result will be in order but missing a couple of elements here and there (they show up in the other half).

Math.random.between = (min, max) => Math.floor(Math.random()*(max-min+1)+min);

function* letters () {
  let offset = 0
  while (offset < 26)
    yield String.fromCharCode(65 + offset++)
}

function* randomizeGen (gen) {
   let cache = [];
   let current = gen.next();
   
   while (!current.done) {
    if (Math.random.between(0, 1) > 0.5) {
      yield current.value;
    } else {
      cache.push(current);
    }
    current = gen.next();
   }
   
   while (cache.length > 0) {
    const index = Math.random.between(0, cache.length-1);
    const v = cache[index];
    cache = cache.filter((_,i) => i !== index);
    yield v.value;
   }
}

const randomOrder = Array.from(randomizeGen(letters()));
console.log(randomOrder);