Obtain all integer partitions for a given integer

Is there a way to compute all integer partitions for a given integer?

For example n=4

we have

4+ 0 + 0 +0
3+ 1 + 0 +0
2+ 2 + 0 +0
2+ 1 + 1 +0
1+ 1 + 1 +1

I would like to obtain a matrix

[4, 0, 0, 0;
3, 1, 0, 0;
2, 2, 0, 0;
2, 1, 1, 0;
1, 1, 1, 1]

Answer 1

[Matt J]

This seems to do it. It uses NSUMK ( Download ). For example,

   [~,x] = nsumk(4,4);

   result=flipud(unique(sort(x,2,'descend'),'rows'))

leads to,

result =
   4     0     0     0
   3     1     0     0
   2     2     0     0
   2     1     1     0
   1     1     1     1

[Michael Vaughan]

Hey man, so I'm a complete noob at MatLab. I downloaded this and it looks great, exactly what I need! I open up matlab, and then click "open", and then run the extracted file, nsumk. It opens up a bunch of code that I'm assuming runs the program in an "editor" window. What do I do from here to get this code fully function so that all I must do is type the input and the matrix comes out?

Your time is greatly appreciated!!!

[Walter Roberson]

Save the nsumk.m file in a convenient directory that is not under the MATLAB installation directory. Use pathtool to add that directory to your MATLAB path. Now you can call upon the code from any of your programs.

Alternately, if you have a MATLAB from the last few years, go to the command window and select Add-Ons -> Get Add-Ons . In the search bar of that page that comes up, type in nsumk . A page of results will come up. Click on the nsumk area to bring up a description of the program. Over on the right hand side, click Add -> Add To MATLAB. Click to agree to the license. MATLAB will now download the code and install it for you so that it is accessible to any of your programs.

[Michael Vaughan]

Okay, so I added the directory that contains the scripts to a path using addpath. So, i'm trying to type a bunch of different things into the command window ,but can't get the program to run. Can you give me an example to copy and paste into the command window now that I've added the path?

[Michael Vaughan]

I'm copying and pasting what the original poster typed into the command prompt, that is:

   [~,x] = nsumk(4,4);
   result=flipud(unique(sort(x,2,'descend'),'rows'))

and i'm not getting any good output. It's getting an error

Error: File: nsumk.m Line: 11 Column: 53

Invalid expression. Check for missing multiplication operator, missing or unbalanced delimiters, or other syntax error. To

construct matrices, use brackets instead of parentheses.

[Walter Roberson]

Line 11 of nsumk.m is a comment, so that does not make any sense

%    is a natural way to list coefficients of polynomials in N variables of degree K.

unless you also provided your own nsumk.m ?

Also, which MATLAB version are you using?

Answer 2

[Bruno Luong]

I wrote a short function that doesn't need to post-proceesed with UNIQUE (wast of time and memory) when using with NSUMK or allvL1 (order matter)

function v = Partition(n, lgt)
% v = Partition(n)
% INPUT
%   n: non negative integer
%   lgt: optional non negative integer
% OUTPUT:
%   v: (m x lgt) non-negative integer array such as sum(v,2)==n
%       each row of v is descending sorted
%       v contains all possible combinations
%       m = P(n) in case lgt == n, where P is the partition function
%       v is (dictionnary) sorted
% Algorithm:
%    Recursive
% Example:
% >> Partition(5)
% 
% ans =
% 
%      5     0     0     0     0
%      4     1     0     0     0
%      3     2     0     0     0
%      3     1     1     0     0
%      2     2     1     0     0
%      2     1     1     1     0
%      1     1     1     1     1

if nargin < 2
    lgt = n;
end
v = PartR(lgt+1, n, Inf);

end % Partition

%% Recursive engine of integer partition
function v = PartR(n, L1, head)
rcall = isfinite(head);
if rcall
    L1 = L1-head;
end
if n <= 2
    if ~rcall
        v = L1;
    elseif head >= L1
        v = [head, L1];
    else
        v = zeros(0, n, class(L1));
    end
else % recursive call
    j = min(L1,head):-1:0;
    v = arrayfun(@(j) PartR(n-1, L1, j), j(:), 'UniformOutput', false);
    v = cat(1,v{:});
    if rcall
        v = [head+zeros([size(v,1),1], class(head)), v];
    end
end
end % PartR