优化repeater嵌套场景下rangePowerSet生成器的计算效率

我将介绍两个用JavaScript实现的生成器（问题具备通用性）：

• 第一个生成器permutationPicks，用于生成从0（包含）到size（不包含）的整数集中选取numPicks个元素的所有排列组合，示例代码如下：

let permutationPicks = function*(size, numPicks, progress=[]) {
    if (numPicks === 0) {
        yield progress;
        return;
    }
    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'));

• 第二个生成器rangePowerSet，接收两个范围参数range1和range2，每个范围格式为{ start, end }（start、end为非负整数且end >= start，范围包含两端整数，例如{ start: 3, end: 7 }包含3到7）。

结合模块化节点系统理解：节点有类型和执行逻辑，其中repeater类型节点包含一个范围和子节点，执行时会随机将子节点执行n次（n在自身范围内）。rangePowerSet用于计算：当节点george嵌套在range2的repeater中，再嵌套在range1的repeater中（即repeater(range1, repeater(range2, george))），执行最外层repeater时，george所有可能的执行次数。

示例：

• 当range1 = { start: 2, end: 5 }，range2 = { start: 4, end: 4 }时，george的执行次数为[8, 12, 16, 20]；
• 当range1 = { start: 1, end: 4 }，range2 = { start: 3, end: 4 }时，可行次数为[3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]，存在间隙。

当前rangePowerSet通过枚举所有组合计算，范围参数稍大时效率极低。

我已观察到以下规律：

• range1.start * range2.start是george执行次数的下限（repsLo），range1.end * range2.end是上限（repsHi）；
• repsLo到repsHi之间的多数数值都是可行的；
• 当其中一个范围宽度为1时，可行区间常存在间隙，但即使两个范围都较宽，也可能出现间隙。

我仍有以下疑问：

1. 交换range1和range2后结果不同的内在逻辑；
2. 可行区间出现间隙的具体条件；
3. 三层及以上repeater嵌套的计算规律；

核心需求是提升rangePowerSet的性能，请问如何优化该生成器？是否存在闭式解法？

一、交换range1和range2结果不同的逻辑 #

嵌套顺序决定了次数的约束层次：

• 原场景：先选外层重复次数k（k ∈ range1），再选k个内层重复次数（每个∈ range2），总次数为这k个数的和。即总次数是**k个[range2.start, range2.end]区间内整数的和**，k可取range1内任意整数。
• 交换后场景：先选外层重复次数m（m ∈ range2），再选m个内层重复次数（每个∈ range1），总次数为这m个数的和。即总次数是**m个[range1.start, range1.end]区间内整数的和**，m可取range2内任意整数。

两种场景的求和约束完全不同，因此结果集合可能存在差异。例如：

• range1=[1,2]，range2=[3,4]
  • 原场景结果：k=1时为3,4；k=2时为6,7,8 → 集合{3,4,6,7,8}
  • 交换后结果：m=3时为3,4,5,6；m=4时为4,5,6,7,8 → 集合{3,4,5,6,7,8}
    可见交换后新增了5这个可行值。

二、可行区间出现间隙的具体条件 #

对于单个k（∈ range1），k个[c,d]（c=range2.start，d=range2.end）整数的和的范围是[k*c, k*d]，且该区间内所有整数均可达（通过调整其中一个数的取值，可覆盖整个区间）。

整个可行集合是所有k ∈ [a,b]（a=range1.start，b=range1.end）对应的区间[k*c, k*d]的并集。间隙出现的核心条件是：

存在相邻的k值（k ∈ [a, b-1]），使得(k+1)*c > k*d + 1

即前一个k对应的区间上限k*d，与后一个k+1对应的区间下限(k+1)*c之间存在断层（差值大于1），断层内的数值均不可达。

示例：range1=[1,4]，range2=[3,4]

• k=1的区间上限为4，k=2的区间下限为6，6 > 4+1，因此5是间隙值。

当range2为单点区间（c=d）时，(k+1)*c = k*c + c，k*d +1 = k*c +1，若c>1，则必然满足(k+1)*c > k*d +1，因此可行集合必然存在间隙（如用户给出的第一个示例）。

三、三层及以上repeater嵌套的计算规律 #

三层嵌套（如repeater(range1, repeater(range2, repeater(range3, george)))）的总次数逻辑可逐层推导：

1. 第一层（最内层）：george的单次内层执行次数是p ∈ range3，m次执行的和为m个p的和，范围是[m*e, m*f]（e=range3.start，f=range3.end）；
2. 第二层：外层执行k ∈ range1次，每次选m ∈ range2，总次数为k个[m*e, m*f]区间的和的集合，等价于总次数为N个p的和（N是k个m的和，N ∈ S2，S2是两层嵌套range1和range2得到的可行次数集合）；
3. 最终可行集合是所有N ∈ S2对应的区间[N*e, N*f]的并集。

多层嵌套的复杂度会显著提升，但核心逻辑仍是基于前一层的可行区间集合，迭代计算当前层的区间并集，无需枚举所有组合。

四、rangePowerSet的优化方案与闭式解法 #

优化方案：区间合并算法 #

放弃枚举所有组合，转而利用“单个k对应连续区间”的特性，通过合并区间得到可行集合，时间复杂度为O(b-a+1)，内存占用极低。

JavaScript生成器实现示例：

function* rangePowerSet(range1, range2) {
    const { start: a, end: b } = range1;
    const { start: c, end: d } = range2;
    let currentLeft, currentRight;

    for (let k = a; k <= b; k++) {
        const left = k * c;
        const right = k * d;

        if (currentLeft === undefined) {
            currentLeft = left;
            currentRight = right;
        } else {
            // 合并重叠或连续的区间
            if (left <= currentRight + 1) {
                currentRight = Math.max(currentRight, right);
            } else {
                // 生成当前区间的所有数
                for (let num = currentLeft; num <= currentRight; num++) {
                    yield num;
                }
                currentLeft = left;
                currentRight = right;
            }
        }
    }

    // 生成最后一个区间的数
    if (currentLeft !== undefined) {
        for (let num = currentLeft; num <= currentRight; num++) {
            yield num;
        }
    }
}

闭式解法 #

对于两层嵌套的情况，不存在直接写出所有可行数的简洁表达式，但可以通过合并后的区间集合进行闭式描述：

可行数集合为所有满足存在k ∈ [a,b]，使得k*c ≤ x ≤k*d的整数x，即∪_{k=a}^b [k*c, k*d]

通过计算连续的k区间（满足(k+1)*c ≤k*d +1），可将多个小区间合并为大区间，从而快速描述可行集合。

对于三层及以上嵌套，可通过迭代应用区间合并算法实现高效计算，无需枚举组合，这是当前最可行的高效解法。

内容的提问来源于stack exchange，提问作者Gershom Maes