# Obtain all integer partitions for a given integer

44 views (last 30 days)
Farid Salazar Wong on 1 Jul 2015
Edited: Bruno Luong on 19 Sep 2020
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]

Matt J on 1 Jul 2015
This seems to do it. It uses NSUMK ( Download ). For example,
[~,x] = nsumk(4,4);
result=flipud(unique(sort(x,2,'descend'),'rows'))
result =
4 0 0 0
3 1 0 0
2 2 0 0
2 1 1 0
1 1 1 1

Michael Vaughan on 19 Sep 2020
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 on 19 Sep 2020
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 on 19 Sep 2020
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?

Bruno Luong on 19 Sep 2020
Edited: Bruno Luong on 19 Sep 2020
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)
if rcall
end
if n <= 2
if ~rcall
v = L1;
else
v = zeros(0, n, class(L1));
end
else % recursive call
v = arrayfun(@(j) PartR(n-1, L1, j), j(:), 'UniformOutput', false);
v = cat(1,v{:});
if rcall
end
end
end % PartR