I'm trying to create a generator that yields values between a given range. My requirements are:
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!
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');
}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%)`;
}