List of vectors, whose sum of elements equal to the loop variable

Question

I want to create a list of vectors, where the elements of each vector in the list sums up to the loop variable without considering order of elements and repetition into account. For eg.

k=1, list ={[1]}; 
k=2, list ={[1,1],[2]}; 
k=3, list ={[1,1,1],[1,2],[2,1],[3]}; 
k=4, list ={[1,1,1,1],[1,3],[3,1],[2,2],[2,1,1],[1,2,1],[1,1,2],[4]};

and so on. The length of the list is $2^{k-1}$. Is there any easy strategy to do this in MATLAB?

close relation: https://stackoverflow.com/questions/21500539/combinations-totaling-to-sum, you are looking for "partitions" of the integer https://en.wikipedia.org/wiki/Partition_(number_theory), looks like there are already fileexchange functions to do this e.g. https://uk.mathworks.com/matlabcentral/fileexchange/12009-partitions-of-an-integer — Wolfie, May 03 '22 at 11:34
Why are `[2, 1]` and `[1, 2]` seen separately? That'd nearly suggest that `[1, 1]` and `[1, 1]` are distinct as well. You can just use a recursive function, starting with `[1]`, then add a `[1]` to each list already present and add the `[2]` etc. Check for lists with non-unique numbers and `randperm()` them. Note though, that this list will get very big very fast, i.e. you won't get far beyond `k=20` based on RAM alone. — Adriaan, May 03 '22 at 11:38

flawr · Accepted Answer · 2022-05-03T12:21:51.033

There is an easy recursive strategy: If you have a list of the integer partitions with the sum of some k-1, it is easy to generate the partitions with sum k: Given some partition, we can either append an 1 to create a new partition, or we can just increment the last entry., so something like this should work.

k = 5;
sumk = {[1]}; % anchor
for current_sum = 2:k    % recursion
    new_sumk = {};
    % (a) create new list by appending an 1
    new_append = cellfun(@(x)[x,1], sumk, 'Un', 0);
    % (b) create new list by increasing last element
    new_increment = cellfun(@(x)[x(1:end-1), x(end)+1], sumk, 'Un', 0)
    sumk = [new_append, new_increment];
end

% print the whole thing:
for l = 1:length(sumk)
    disp(sumk{l})
end

List of vectors, whose sum of elements equal to the loop variable

1 Answers1