Optimize calculation related to `repeater(range1, repeater(range2, george))`

Question

Background

Hello, let me introduce two generators. (I'm using javascript but this problem is generic!)

First this generator permutationPicks yields all possible ways to pick numPicks items from a set of integers from 0 (inclusive) to size (exclusive). See the example:

let permutationPicks = function*(size, numPicks, progress=[]) {
  
  if (numPicks === 0) return yield progress;
  
  for (let v = 0; v < size; v++)
    yield* permutationPicks(size, numPicks - 1, [ ...progress, v ]);
  
};

console.log(`Pick two from size 3:`);
console.log([ ...permutationPicks(3, 2) ].map(v => v.map(v => v.toString()).join(',')).join('\n'));

console.log(`Pick three from size 4:`);
console.log([ ...permutationPicks(4, 3) ].map(v => v.map(v => v.toString()).join(',')).join('\n'));

Second this generator rangePowerSet takes two ranges, range1 and range2, each of which look like { start, end }, where start and end are integers >= 0 and end >= start; note that in this context ranges will be interpreted as inclusive on both ends (the range { start: 3, end: 7 } excludes 2 and 8, and contains 3 and 7).

A preamble may help understand this function. Consider a system of modular nodes. Nodes have a "type" and may "execute"; the "type" determines how "execution" occurs. One type of node is a "repeater", which has a "range" and a "child node"; when a "repeater" executes, it delegates execution to its child node a random number of times n, where n is within the repeater's range.

Now we can begin to understand rangePowerSet. If we have an arbitrary node george nested in a repeater with range1, nested in another repeater with range2 (overall: repeater(range1, repeater(range2, george))) and we execute the outermost repeater, what are all the possibilities for how many times george may execute?

Let's think about it for a second. Given:

range1 = { start: 2, end: 5 }
range2 = { start: 4, end: 4 }
george may execute [ 8, 12, 16, 20 ] times

Note range2 only contains 4; range1 repeats this 4 by [ 2, 3, 4, 5 ] times.

Things are less intuitive when both ranges are "wide"; consider:

range1 = { start: 1, end: 4 }
range2 = { start: 3, end: 4 }
george may execute [ 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 ] times

In this case george executes anywhere between 0 and 16 times, excluding [ 0, 1, 2, 5 ]. There is a bit of chaos here and I feel I'm verging into tricky number theory.

Overall rangePowerSet performs this calculation. Running the example will randomize range1 and range2, and solve the number of times george may execute.

let permutationPicks = function*(size, numPicks, progress=[]) {

  if (numPicks === 0) return yield progress;

  for (let v = 0; v < size; v++)
    yield* permutationPicks(size, numPicks - 1, [ ...progress, v ]);

};
let rangePowerSet = function*(range1, range2) {
  
  for (let outer = range1.start; outer <= range1.end; outer++) {
    
    // `outer` determines how many times we pick values in `range`
    // We add together all such picked values
    
    let range2Size = range2.end - range2.start + 1; // Add 1; ranges are inclusive on both ends
    for (let pick of permutationPicks(range2Size, outer))
      // `pick` contains indices from a range the same size as `range2`, but starting
      // from `0` (instead of `range2.start`); compensate for this offset and then add
      // all the picks together
      yield pick.map(v => range2.start + v).reduce((m, v) => m + v, 0);
    
  }
  
};

let rand = (a, b) => a + Math.floor((b - a) * Math.random());

let a = rand(0, 4);
let b = a + rand(0, 5);

let c = rand(0, 4);
let d = c + rand(0, 5);

let vals = [ ...rangePowerSet({ start: a, end: b }, { start: c, end: d }) ];
let set = [ ...new Set(vals) ].sort((a, b) => a - b);
let max = set.at(-1);

console.log(`range1 = { start: ${a}, end: ${b} }`);
console.log(`range2 = { start: ${c}, end: ${d} }`);
console.log(`Possible repetitions: ${set.join(', ')}`);
console.log('Visualization:');
console.log(`(0) ${' '.repeat(max + 1).split('').map((v, i) => set.includes(i) ? '\u2022' : '-').join('')} (${max})`);

Each run of the above code computes the number of times george may run with the setup repeater(range1, repeater(range2, george)), and where range1 and range2 are quite small ranges. Note a diagram is also output which may look like:

(0) ------•--• (9)

In the sequence ------•--• each char indicates whether george may repeat a number of times equal to that char's index (0-based); - indicates "impossible", while • indicates "possible". This specific sequence indicates that george can only execute exactly 6 or 9 times.

Note you may have to run the example some 30+ times in order to see good examples of "unexpected" / "chaotic" results.

Note that rangePowerSet's output is not always ordered, and may contain the same value multiple times (representing different repetition values for the inner and outer repeaters which happened to multiply to the same value). In the above code's output the values are unique-ified and sorted before being displayed.

Problem

I want to better understand the dynamics of this problem. I have already observed the following:

• range1.start * range2.start is the lower bound (repsLo), and range1.end * range2.end is the higher bound (repsHi), of how many times george can repeat
• The range of possibilities between repsLo and repsHi (reps) is often fully covered
• When reps is not fully covered, it's often because the width of either range1 or range2 is 1 (only containing a single value), but it's possible for reps to have gaps even when both ranges are "wide" - for example, consider the following:

range1 = { start: 1, end: 4 }
range2 = { start: 3, end: 4 }
(0) ---••-••••••••••• (16)

range1 = { start: 1, end: 2 }
range2 = { start: 3, end: 4 }
(0) ---••-••• (8)

range1 = { start: 0, end: 2 }
range2 = { start: 3, end: 4 }
(0) •--••-••• (8)

range1 = { start: 0, end: 2 }
range2 = { start: 5, end: 6 }
(0) •----••---••• (12)

range1 = { start: 1, end: 4 }
range2 = { start: 5, end: 6 }
(0) -----••---•••--••••-••••• (24)

range1 = { start: 2, end: 6 }
range2 = { start: 5, end: 6 }
(0) ----------•••--••••-••••••••••••••••• (36)

I fail to understand:

• The dynamics of when range1 and range2 are swapped (this often gives different results)
• The exact circumstances under which reps contains gaps
• The dynamics of nesting three or more "repeaters" (but I suspect this becomes very, very complicated??)

Overall (and to focus this question so that it doesn't get closed) I am interested to improve the performance of rangePowerSet. Right now it is far too inefficient when the range parameters are even a bit large.

Overall, how can rangePowerSet be made more efficient? Is there any chance there's a closed-form-type solution to this?