How can I simplify this generator to eliminate the recursion?-CodePudding

I'm trying to create a generator that yields values between a given range. My requirements are:

all emitted values are unique
the order of values is the same every time the generator is run
each value is far away from previously emitted values
it is not known how many values will be generated

I've decided to model this as a tree, and doing something like a breadth first search to split the range up into even sized subdivisions, and iterating over each layer in an order that avoids adjacent node visiting.

I've come up with the following solution which works, however I don't like that it is using recursion, and I suspect it can be rewritten to eliminate the recursion (maybe a queue?) A bit stuck here. Here's what I have so far:

function* orderedSubdivisor(start: number, end: number): Generator<number> {

    const mid = (end - start) / 2   start
    
    yield mid

    const left = orderedSubdivisor(start, mid)
    const right = orderedSubdivisor(mid, end)

    while (true) {
      yield left.next().value
      yield right.next().value  
    }
}

const iter = orderedSubdivisor(0, 64)

console.log(Array.from({length: 63}, () => iter.next().value))

thanks!

CodePudding user response：

You can model this using a binary counter to represent the position/path in your tree. The least significant bit decides whether you are in the left or right half of the top branch, the second-least significant bit decides whether you are in the left or right half on the second level, and so on:

function* orderedSubdivisor(start, end) {
    for (let i=1; true; i  ) {
        let sum = start;
        let part = end-start;
        for (let j=i; j; j=j>>>1) {
            part /= 2;
            if (j & 1) sum  = part;
        }
        yield sum;
    }
}

const iter = orderedSubdivisor(0, 64)

console.log(Array.from({length: 63}, () => iter.next().value))

In fact you can see that you've essentially just created a counter, but flip the bit order of every yielded value:

function* orderedSubdivisor(start, end) {
  const mid = (end - start) / 2   start
  yield mid
  const left = orderedSubdivisor(start, mid)
  const right = orderedSubdivisor(mid, end)
  while (true) {
    yield left.next().value
    yield right.next().value  
  }
}

let i=0;
for (const v of orderedSubdivisor(0, 64)) {
  if (i   >= 63) break;
  document.body.appendChild(document.createElement('pre')).textContent = v.toString(10).padStart(2) ': 0b' v.toString(2).padStart(6, '0');
}

CodePudding user response：

I'm trying to create a generator that yields values between a given range. My requirement [is] to have each value far away from previously emitted values.
My actual use case is mapping to hues in a colour wheel.

For that, I recommend the fibonacci hashing technique with the golden ratio/golden angle, which provides a very evenly distributed output around the colour wheel:

function* orderedSubdivisor(start, end) {
  for (let i=0; true; i =0.6180339887498951) {
    yield start (i%1)*(end-start);
  }
}

let i=0;
for (const v of orderedSubdivisor(0, 360)) {
  if (i   >= 100) break;
  const p = document.body.appendChild(document.createElement('p'));
  p.textContent = v;
  p.style = `background-color: hsl(${v}deg, 100%, 50%)`;
}