Thread Subject:

All possible permutations that sum up to a number

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.

"Joo" <pilgrimhere@_REMOVETHIS_lycos.com> 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)]

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.

Ken Davis wrote:
>
>
> "Joo" <pilgrimhere@_REMOVETHIS_lycos.com> 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.

In article <ef4fcd1.2@webcrossing.raydaftYaTP>, Joo
<pilgrimhere@_REMOVETHIS_lycos.com> wrote:

> Ken Davis wrote:
> >
> > "Joo" <pilgrimhere@_REMOVETHIS_lycos.com> 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

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???

ehsanbarghi <barghi.ehsan@gmail.com> wrote in message <gv2dnWI_GqYcBJXNnZ2dnUVZ_qqdnZ2d@giganews.com>...
> 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

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