迭代多项式展开中的索引

Question

上下文：在多项式展开中，每一项的有效索引 [k1, k2, ... kr] 满足方程 n = k1 + k2 + ... + kr。给定 r 和 n，我尝试迭代所有项。为此，我需要一种方法来获取每个有效的索引集。

r = 2 且 n = 3 的示例：

[0 3], [1 2], [2 1], [3 0]

我尝试将有效数组视为基数为 n+1 的数字，其中我将基数中的数字增加 1，然后检查所有数字的总和是否等于 n。

为了节省时间和内存，我的函数不将 r 和 n 作为输入，而仅将先前的有效索引集作为输入。

function out_set = getNextExponent(inp_set) 
    % inp_set is a valid exponent
    % returns the next valid exponent set of a multinomial expansion
    % Examples:
    % getNextExponent([0, 0, 3]) = [0, 1, 2]
    % getNextExponent([0, 2, 1]) = [1, 1, 1]
    % getNextExponent([3, 0, 0]) = error
    % disp(getNextExponent([1, 0, 3, 5, 0])) = [1, 0, 4, 0, 4]
    % disp(getNextExponent([100, 29, 29, 0, 0, 0])) = [100, 30, 0, 0, 0, 28]
    
    % Get the parameters
    n = sum(inp_set); 
    base = n+1; % exponent list is a number in base n+1

    % Check if it is the last valid index set
    out_set = zeros(size(inp_set));
    out_set(1) = n;
    if isequal(inp_set, out_set)
        error('Last exponent already reached')
    end

    % Loop until next valid set is found
    while true
        % Add one to the set
        carry = 1;
        index = length(inp_set);
        while carry == 1
            if inp_set(index)+1 < base
                inp_set(index) = inp_set(index)+1;
                carry = 0;
            else 
                inp_set(index) = 0;
                index = index-1;
            end
        end
        % Is the next valid exponent reached?
        if sum(inp_set) == n
            break;
        end
    end    
    out_set = inp_set;
end

然而，这是极其低效的。是否有更好的方法来迭代每个有效集？

---

编辑：我不知道这是否有帮助，但这与将n个相同的对象放入r框中是同一个问题。所以可能的数组数量总是（n+r-1 选择 r-1）。

Answer 1

安装 Matt Fig 编写的

combinator.m

以及相关的支持文件。

combinator.m

可以在这里

正如您已经指出的那样，您的问题与解决

n+r-1

选择

r-1

组合（不重复）相同。

请评论

combinator.m

是否有助于加快你的速度