CODEWITHSUNDEEP
matlabvector
MikeL
MikeL

Reputation: 2459

Iterating over all integer vectors summing up to a certain value in MATLAB?

I would like to find a clean way so that I can iterate over all the vectors of positive integers of length, say n (called x), such that sum(x) == 100 in MATLAB.

I know it is an exponentially complex task. If the length is sufficiently small, say 2-3 I can do it by a for loop (I know it is very inefficient) but how about longer vectors?

Thanks in advance,

Upvotes: 5

Views: 468

Answers (2)

Chris Taylor
Chris Taylor

Reputation: 47392

Here is a quick and dirty method that uses recursion. The idea is that to generate all vectors of length k that sum to n, you first generate vectors of length k-1 that sum to n-i for each i=1..n, and then add an extra i to the end of each of these.

You could speed this up by pre-allocating x in each loop.

Note that the size of the output is (n + k - 1 choose n) rows and k columns.

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

Edit

As alluded to in the comments, this will run into memory issues for large n and k. A streaming solution is preferable, which generates the outputs one at a time. In a non-strict language like Haskell this is very simple -

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)]

viz.

>> 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]

which runs virtually instantaneously - no memory issues to worry about.

In Python you could achieve something nearly as simple using generators and the yield keyword. In Matlab it is certainly possible, but I leave the translation up to you!

Upvotes: 2

Luis Mendo
Luis Mendo

Reputation: 112659

This is one possible method to generate all vectors at once (will give memory problems for moderately large 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

Now you can iterate over those vectors:

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

To avoid memory problems it is better to generate each vector as needed, instead of generating all of them initially. The following approach iterates over all possible n-vectors in one for loop (regardless of n), rejecting those vectors whose sum is not the desired value:

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

Upvotes: 1

Related Questions