多项式展开中有效索引集的高效迭代方法求解

问题背景 #

多项式展开中，有效索引集[k₁, k₂, …, kᵣ]满足n = k₁ + k₂ + … + kᵣ，需要遍历所有这类非负整数数组。原方法将数组视为n+1进制数递增后检查和是否为n，但大量无效计算导致效率极低，尤其当n和r较大时。

优化方案1：一次性生成所有有效索引集 #

利用“星条模型”：将问题转化为在n个星和r-1个条的排列中，枚举所有条的位置，再计算每个区间的星数（即对应索引值）。这种方法直接基于组合数生成，无无效计算，效率极高。

MATLAB实现代码：

function all_sets = generateAllExponents(n, r)
    % 生成所有满足k1+k2+...+kr = n的非负整数数组
    % 输入: n-总和, r-数组长度
    % 输出: 每行一个有效索引集
    if r == 1
        all_sets = n;
        return;
    end
    % 生成r-1个分隔符的位置（从n+r-1个位置中选）
    sep_positions = nchoosek(1:(n+r-1), r-1);
    total = size(sep_positions, 1);
    all_sets = zeros(total, r);
    % 计算每个索引集的元素
    for i = 1:total
        % 补全首尾分隔符位置，方便计算区间长度
        seps = [0, sep_positions(i,:), n+r];
        for j = 1:r
            all_sets(i,j) = seps(j+1) - seps(j) - 1;
        end
    end
end

优化方案2：高效生成下一个有效索引集 #

如果不需要一次性生成所有集合，而是逐个迭代，可以直接基于当前集合计算下一个符合原代码顺序的有效集合，完全避免无效的递增检查。

核心思路：

1. 计算当前数组的后缀和，快速确定右侧元素的总和
2. 从右往左找到第一个可调整的位置，将该位置元素加1，同时将右侧所有元素重置为0，仅保留最后一个元素为右侧总和减1（保证总和不变，且生成的数值是大于当前的最小值）

MATLAB实现代码：

function out_set = getNextExponentFast(inp_set)
    n = sum(inp_set);
    r = length(inp_set);
    
    % 检查是否已到最后一个有效集合
    if inp_set(1) == n && all(inp_set(2:r) == 0)
        error('Last exponent already reached');
    end
    
    % 计算从右到左的后缀和
    suffix_sum = zeros(1, r);
    suffix_sum(r) = inp_set(r);
    for i = r-1:-1:1
        suffix_sum(i) = suffix_sum(i+1) + inp_set(i);
    end
    
    % 从右往左找第一个可调整的位置
    for i = r-1:-1:1
        current_k = inp_set(i);
        right_total = suffix_sum(i+1);
        % 调整当前位置元素，同时保证右侧总和减少1
        new_k_i = current_k + 1;
        % 构造新集合：当前位置+1，右侧除最后一个元素外全为0，最后一个元素为右侧总和-1
        out_set = inp_set;
        out_set(i) = new_k_i;
        out_set(i+1:r-1) = 0;
        out_set(r) = right_total - 1;
        % 若最后一个元素非负（必然成立，因为right_total >=1才能进入此分支）
        if out_set(r) >= 0
            return;
        end
    end
end

测试示例：

• getNextExponentFast([0,0,3]) 返回 [0,1,2]
• getNextExponentFast([1,0,3,5,0]) 返回 [1,0,4,0,4]
• getNextExponentFast([100,29,29,0,0,0]) 返回 [100,30,0,0,0,28]（与用户示例一致）

复杂度对比 #

• 原方法：最坏情况下每次生成下一个集合需要O((n+1)^r)次无效递增，复杂度极高
• 优化方案1：时间复杂度为O(C(n+r-1, r-1)*r)，仅与有效集合总数和数组长度相关
• 优化方案2：每次生成下一个集合的时间复杂度为O(r)，无无效计算

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