在MATLAB中迭代所有整数向量的总和到某个值？

Question

我想找到一种干净的方法，这样我就可以迭代所有长度为正整数的向量，比如n (称为x)，比如MATLAB中的sum(x) == 100。

我知道这是一项极其复杂的任务。如果长度足够小，比方说2-3，我可以用for循环(我知道它效率很低)，但是更长的向量呢？

提前谢谢你，

Answer 1

下面是一个使用递归的快速而粗糙的方法。其思想是，要生成长度为k且总和为n的所有向量，首先为每个i=1..n生成长度为k-1且总和为n-i的向量，然后在每个向量的末尾添加额外的i。

您可以通过在每个循环中预先分配x来加速此过程。

注意，输出的大小是(n +k-1选择n)行和k列。

function x = genperms(n, k)

if k == 1
    x = n;
elseif n == 0
    x = zeros(1,k);
else
    x = zeros(0, k);
    for i = 0:n
        y = genperms(n-i,k-1);
        y(:,end+1) = i;
        x = [x; y];
    end
end

编辑

正如评论中提到的，这将遇到大型n和k的内存问题。流式解决方案更可取，它一次生成一个输出。在像Haskell这样的非严格语言中，这非常简单--

genperms n k
    | k == 1    = return [n]
    | n == 0    = return (replicate k 0)
    | otherwise = [i:y | i <- [0..n], y <- genperms (n-i) (k-1)]

也就是

>> mapM_ print $ take 10 $ genperms 100 30
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,100]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,99]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,98]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,97]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,96]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,95]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,6,94]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,7,93]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,92]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,9,91]

它几乎是瞬间运行的--没有内存问题需要担心。

在Python中，您可以使用生成器和yield关键字来实现几乎同样简单的功能。在Matlab中，这当然是可能的，但我将翻译留给您！

Answer 2

这是一种可以一次生成所有向量的方法(对于中等大的n，会出现内存问题)：

s = 10; %// desired sum
n = 3; %// number of digits
vectors = cell(1,n);
[vectors{:}] = ndgrid(0:s); %// I assume by "integer" you mean non-negative int
vectors = cell2mat(cellfun(@(c) reshape(c,1,[]), vectors, 'uni', 0).');
vectors = vectors(:,sum(vectors)==s); %// each column is a vector

现在您可以遍历这些向量：

for vector = vectors %// take one column at each iteration
    %// do stuff with the vector
end

为了避免内存问题，最好根据需要生成每个向量，而不是一开始就生成所有向量。以下方法在一个for循环中迭代所有可能的n-vectors (不考虑n)，拒绝那些和不是所需值的向量：

s = 10; %// desired sum
n = 3;; %// number of digits
for number = 0: s^n-1
    vector = dec2base(number,s).'-'0'; %// column vector of n rows
    if sum(vector) ~= s
        continue %// reject that vector
    end
    %// do stuff with the vector
end