Obtain all integer partitions for a given integer

16 visualizaciones (últimos 30 días)
Farid Salazar Wong
Farid Salazar Wong el 1 de Jul. de 2015
Editada: Bruno Luong el 19 de Sept. de 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]

Respuestas (2)

Matt J
Matt J el 1 de Jul. de 2015
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
  5 comentarios
Michael Vaughan
Michael Vaughan el 19 de Sept. de 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
Walter Roberson el 19 de Sept. de 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?

Iniciar sesión para comentar.


Bruno Luong
Bruno Luong el 19 de Sept. de 2020
Editada: Bruno Luong el 19 de Sept. de 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)
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

Categorías

Más información sobre Search Path en Help Center y File Exchange.

Etiquetas

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by