Obtain all integer partitions for a given integer

Question

Farid Salazar Wong 2015-7-1

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/226437-obtain-all-integer-partitions-for-a-given-integer

编辑： Bruno Luong 2020-9-19

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]

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Matt J 2015-7-1

2
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/226437-obtain-all-integer-partitions-for-a-given-integer#answer_184749

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 =
   0     0     0
   1     0     0
   2     0     0
   1     1     0
   1     1     1

5 个评论
显示 3更早的评论隐藏 3更早的评论

Michael Vaughan 2020-9-19

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 2020-9-19

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 2020-9-19

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/226437-obtain-all-integer-partitions-for-a-given-integer#answer_497158

编辑：Bruno Luong 2020-9-19

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