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

Question

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,

As you say, it's exponential. If you avoid the `for` loop you will be generating all vectors at once, and you will soon encounter memory limitations. — Luis Mendo, Dec 05 '13 at 14:59
It's not actually exponential - the scaling law is approx `n^k` as `n` goes to infinity, for vectors of length `k` that sum to `n`. — Chris Taylor, Dec 05 '13 at 15:20
@PBM When you say *integer vectors*, what exactly do you mean? Is it that all their elements are integers or *positive* integers? If it's the former, you'll have an infinite number of solutions... if it's the latter, then it's a variant of the knapsack problem, with the complexity of _O(n*sum)_. — Eitan T, Dec 05 '13 at 15:54
@EitanT I meant the positive integers. I should have been more precise. Sorry! — MikeL, Dec 05 '13 at 16:02
@PBM So it can be reduced to a knapsack problem, where you have a set of 101 possible items (0-100), and you need to find all subsets the sum of which equals 100. This is a classic problem that can be solved in pseudo-polynomial time using dynamic programming. — Eitan T, Dec 05 '13 at 16:11
@EitanT I think a slight difference is that I am looking for all subsets of size `n` such that their sum is equal to 100. Am I right? — MikeL, Dec 05 '13 at 16:13
@PBM Yes, but looks like the same logic can be applied here. I suggest that you read this related question: [Finding all possible combinations of numbers to reach a given sum](http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum)... — Eitan T, Dec 05 '13 at 16:29

Chris Taylor · Answer 1 · 2013-12-05T17:13:30.490

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!

Haha. I meant "quick to write" rather than "quick to run" :) There are certainly implementation details that can speed it up, but I don't think there's a better algorithm (this method generates the minimum number of vectors required to solve the problem, as opposed to generate-and-reject algorithms which will consider many more vectors than are required). — Chris Taylor, Dec 05 '13 at 16:35
Oh, absolutely. If `n` and `k` are large you'll need to do something else. A generate-and-reject algorithm would be simplest, though slow. I'd need to think a little harder to come up with a solution that efficiently generates the vectors one at a time (it'd be much easier in a non-strict language!). — Chris Taylor, Dec 05 '13 at 17:01

Luis Mendo · Answer 2 · 2013-12-05T15:30:35.763

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

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

2 Answers2