# Thread Subject: All possible permutations that sum up to a number

 Subject: All possible permutations that sum up to a number From: Joo Date: 7 Mar, 2007 17:30:13 Message: 1 of 8 Hi, I would like to generate all the possible n-sized permutations that sum up to a particular number d. E.g. n = 3; d = 4 Ans = [ 0 0 4 ;              0 1 3 ;              0 2 2 ;              0 3 1 ;              0 4 0 ;              1 0 3 ;              1 1 2 ;              1 2 1 ;              1 3 0 ;              2 0 2 ;              2 1 1 ;              2 2 0 ;              3 0 1 ;              3 1 0 ;              4 0 0 ] Is there an efficient way of doing this? Thanks.
 Subject: All possible permutations that sum up to a number From: Ken Davis Date: 7 Mar, 2007 18:39:16 Message: 2 of 8 "Joo" wrote in message news:ef4fcd1.-1@webcrossing.raydaftYaTP... > Hi, > > I would like to generate all the possible n-sized permutations that > sum up to a particular number d. > > E.g. n = 3; d = 4 > > Ans = [ 0 0 4 ; > 0 1 3 ; > 0 2 2 ; > 0 3 1 ; > 0 4 0 ; > 1 0 3 ; > 1 1 2 ; > 1 2 1 ; > 1 3 0 ; > 2 0 2 ; > 2 1 1 ; > 2 2 0 ; > 3 0 1 ; > 3 1 0 ; > 4 0 0 ] > > Is there an efficient way of doing this? > > Thanks. >>[d1, d2, d3] = ndgrid(0:4, 0:4, 0:4) >>d = d1+d2+d3 >>i = find(d==4) >>[d1(i),d2(i),d3(i)]
 Subject: All possible permutations that sum up to a num From: Joo Date: 7 Mar, 2007 19:17:56 Message: 3 of 8 Joo wrote: > > > Hi, > > I would like to generate all the possible n-sized permutations that > sum up to a particular number d. > > E.g. n = 3; d = 4 > > Ans = [ 0 0 4 ; > 0 1 3 ; > 0 2 2 ; > 0 3 1 ; > 0 4 0 ; > 1 0 3 ; > 1 1 2 ; > 1 2 1 ; > 1 3 0 ; > 2 0 2 ; > 2 1 1 ; > 2 2 0 ; > 3 0 1 ; > 3 1 0 ; > 4 0 0 ] > > Is there an efficient way of doing this? > > Thanks.
 Subject: All possible permutations that sum up to a num From: Joo Date: 7 Mar, 2007 19:19:16 Message: 4 of 8 Ken Davis wrote: > > > "Joo" wrote in message > news:ef4fcd1.-1@webcrossing.raydaftYaTP... >> Hi, >> >> I would like to generate all the possible n-sized permutations > that >> sum up to a particular number d. >> >> E.g. n = 3; d = 4 >> >> Ans = [ 0 0 4 ; >> 0 1 3 ; >> 0 2 2 ; >> 0 3 1 ; >> 0 4 0 ; >> 1 0 3 ; >> 1 1 2 ; >> 1 2 1 ; >> 1 3 0 ; >> 2 0 2 ; >> 2 1 1 ; >> 2 2 0 ; >> 3 0 1 ; >> 3 1 0 ; >> 4 0 0 ] >> >> Is there an efficient way of doing this? >> >> Thanks. > >>>[d1, d2, d3] = ndgrid(0:4, 0:4, 0:4) >>>d = d1+d2+d3 >>>i = find(d==4) >>>[d1(i),d2(i),d3(i)] > > > Thanks, this is what I need. Is there anyway to modify the code to take arbitrary values of n? Currently, this works only for n=3. Cheers.
 Subject: All possible permutations that sum up to a num Date: 8 Mar, 2007 08:53:28 Message: 5 of 8 In article , Joo wrote: > Ken Davis wrote: > > > > "Joo" wrote in message > > news:ef4fcd1.-1@webcrossing.raydaftYaTP... > >> Hi, > >> > >> I would like to generate all the possible n-sized permutations > > that > >> sum up to a particular number d. > >> > >> E.g. n = 3; d = 4 > >> > >> Ans = [ 0 0 4 ; > >> 0 1 3 ; > >> 0 2 2 ; > >> 0 3 1 ; > >> 0 4 0 ; > >> 1 0 3 ; > >> 1 1 2 ; > >> 1 2 1 ; > >> 1 3 0 ; > >> 2 0 2 ; > >> 2 1 1 ; > >> 2 2 0 ; > >> 3 0 1 ; > >> 3 1 0 ; > >> 4 0 0 ] > >> > >> Is there an efficient way of doing this? > >> > >> Thanks. > > > >>>[d1, d2, d3] = ndgrid(0:4, 0:4, 0:4) > >>>d = d1+d2+d3 > >>>i = find(d==4) > >>>[d1(i),d2(i),d3(i)] > > Thanks, > > this is what I need. Is there anyway to modify the code to take > arbitrary values of n? Currently, this works only for n=3. > > Cheers. -------------------   For general n, having to do a reject becomes increasingly expensive for large n, so here is an algorithm using 'nchoosek' that doesn't do any rejections.   Again, for n columns of non-negative integers with each possible row having a sum of d, do this:  c = nchoosek(1:d+n-1,n-1);  m = size(c,1);  t = ones(m,d+n-1);  t(repmat((1:m).',1,n-1)+(c-1)*m) = 0;  u = [zeros(1,m);t.';zeros(1,m)];  v = cumsum(u,1);  x = diff(reshape(v(u==0),n+1,m),1).'; The desired array is x. Roger Stafford
 Subject: All possible permutations that sum up to a number From: ehsanbarghi Date: 19 Jul, 2012 23:34:25 Message: 6 of 8 hello. i want to produce a table like the above one. but in my table there is not Duplicate rows. like below table: a=[0 0 4;    0 1 3;    0 2 2;    1 1 2]; Is there anybody that can help me???
 Subject: All possible permutations that sum up to a number From: Bruno Luong Date: 20 Jul, 2012 05:34:38 Message: 7 of 8 ehsanbarghi wrote in message ... > hello. > i want to produce a table like the above one. but in my table there is not Duplicate rows. like below table: > a=[0 0 4; > 0 1 3; > 0 2 2; > 1 1 2]; > > Is there anybody that can help me??? > You might use this FEX: http://www.mathworks.com/matlabcentral/fileexchange/17818 >> unique(sort(allVL1(3,4),2),'rows') ans =      0 0 4      0 1 3      0 2 2      1 1 2 % Bruno
 Subject: All possible permutations that sum up to a number From: Bruno Luong Date: 20 Jul, 2012 06:58:15 Message: 8 of 8 I modify the code so it can return directly the unique combination without using the large intermediate results then filter-out. function v = allVL1u(n, L1) % v = allVL1u(n, L1) % All integer permutations with sum criteria % unique combination (after permutation) % % INPUT % n: length of the vector % L1: target L1 norm % L1ops: optional string ('==' or '<=' or '<') % default value is '==' % OUTPUT: % v: (m x n) array such as: sum(v,2) == L1, % each row is sorted % all elements of v is naturel numbers {0,1,...} % v contains all (=m) possible combinations % n = floor(n); % make sure n is integer if n<1     v = [];     return end n = feval(class(L1),n); v = allVL1recurs(n, L1); end % allVL1 %% Recursive engine function v = allVL1recurs(n, L1, head) % Algorithm: % Recursive if n==1     v = L1; else % recursive call     v = cell2mat(arrayfun(@(j) allVL1recurs(n-1, L1-j, j), (0:L1)', ...                  'UniformOutput', false)); end if nargin>=3 % add a head column     v = v(head <= v(:,1), :);     v = [head+zeros(size(v,1),1,class(head)) v]; end end % allVL1recurs % Save the above in the same mfile % Test in command line >> allVL1u(3,4) ans =      0 0 4      0 1 3      0 2 2      1 1 2 >> % Bruno

## Tags for this Thread

### Add a New Tag:

Separated by commas
Ex.: root locus, bode

### What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Feed for this Thread

Contact us