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

Question

我想找到一个干净的方法,以便我可以迭代所有长度正整数的向量,比如说n(调用x),这样sum(x) == 100在MATLAB中.

我知道这是一项指数级复杂的任务.如果长度足够小,比如说2-3我可以通过一个for循环来做(我知道这是非常低效的)但是更长的向量怎么样？

提前致谢,

Answer 1

这是一种使用递归的快速但肮脏的方法。这个想法是，要生成长度k总和为 的所有向量n，首先为每个 生成长度k-1总和为 的向量，然后在每个向量的末尾添加一个额外的向量。n-ii=1..ni

您可以通过在每个循环中进行预分配来加快速度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 中这当然是可能的，但我将翻译留给你！