Dear all goodmorning,

I have a question related to dec2bin.

I am currently using the following in one of my programs to create a
matrix with all the possible 0-1 combinations for a value of n. This
results in a '2^n by n' matrix.

n=3
A=(dec2bin(0:(2^n)-1)=='1');
A

Result
------

A =

     0 0 0
     0 0 1
     0 1 0
     0 1 1
     1 0 0
     1 0 1
     1 1 0
     1 1 1

What I really need is to introduce another variable, say m=2, and
modify the dec2bin command somehow in order for it to produce a
matrix with only the 0-1 combinations for the value of n, that
contain so many 1s equal to m.

So for example, the new matrix based on the example above should be:

A =
     
     0 1 1
     1 0 1
     1 1 0
     
because only these 3 lines contain a 0-1 combination with the number
of 1's equal to m (m=2).

I am currently using the standard dec2bin producing all the possible
combinations, and then I use a 'for' loop that checks every signle
line, does the sum of the line, and if it is greater or less than the
value of m it deletes the line from the matrix. It works ok but it is
very time-consuming.

I was hoping for some modification on the original dec2bin command to
get it to bring ONLY the combinations with the number of 1's equal to
m.

I thank you in advance for your help and comments.

Regards,

P� Thu, 17 Mar 2005 01:58:30 -0500, skrev Antonios  
<antonios.tatarakis@gmail.com>:

> n=3
> A=(dec2bin(0:(2^n)-1)=='1');
> A
>
> Result
> ------
>
> A =
>
>      0 0 0
>      0 0 1
>      0 1 0
>      0 1 1
>      1 0 0
>      1 0 1
>      1 1 0
>      1 1 1
>
<reduce to>
>
> A =
>     0 1 1
>      1 0 1
>      1 1 0


You dont have to use a loop

B=A(sum(A,2)==2,:)

will pick all rows with sum==2


-- 
K

Kristian,

thank you very much for the tip.
Did not think of the simple solution ;-)

A

Antonios wrote:
>
>
<snip, ones and zeros problem...

Another solution, not using dec2bin:

>> n=3;
>> m=2;
>> unique(perms([ones(1,m),zeros(1,n-m)]),'rows')

ans =

     0 1 1
     1 0 1
     1 1 0

In article <eeff439.-1@webx.raydaftYaTP>, Antonios
<antonios.tatarakis@gmail.com> wrote:

> Dear all goodmorning,
> 
> I have a question related to dec2bin.
> 
> I am currently using the following in one of my programs to create a
> matrix with all the possible 0-1 combinations for a value of n. This
> results in a '2^n by n' matrix.
> 
> n=3
> A=(dec2bin(0:(2^n)-1)=='1');
> A
> 
> Result
> ------
> 
> A =
> 
>      0 0 0
>      0 0 1
>      0 1 0
>      0 1 1
>      1 0 0
>      1 0 1
>      1 1 0
>      1 1 1
> 
> What I really need is to introduce another variable, say m=2, and
> modify the dec2bin command somehow in order for it to produce a
> matrix with only the 0-1 combinations for the value of n, that
> contain so many 1s equal to m.
> 
> So for example, the new matrix based on the example above should be:
> 
> A =
>      
>      0 1 1
>      1 0 1
>      1 1 0
>      
> because only these 3 lines contain a 0-1 combination with the number
> of 1's equal to m (m=2).
> 
> I am currently using the standard dec2bin producing all the possible
> combinations, and then I use a 'for' loop that checks every signle
> line, does the sum of the line, and if it is greater or less than the
> value of m it deletes the line from the matrix. It works ok but it is
> very time-consuming.
> 
> I was hoping for some modification on the original dec2bin command to
> get it to bring ONLY the combinations with the number of 1's equal to
> m.
> 
> I thank you in advance for your help and comments.
> 
> Regards,
---------------------
Hello Antonios,

  I found your problem interesting, so I wrote the accompanying function
which loops only through the nCm combinations of m 1-bits among n, instead
of creating larger arrays and then reducing them.  It is possible that for
sufficiently large values of n it would execute faster than the other
algorithms since it is order nCm rather than order 2^n or n!, but I cannot
test it fully on my Student Edition matlab with its 8192-element array
restriction.  In any case, feel free to use it if you like.  I've checked
it out as far as n = 11 and it appears to function properly.

%----------------
function x = bincomb(n,m);

% This generates all possible binary numbers
% with m ones and n-m zeros as rows in the
% nCm x n matrix x, where nCm is the number of
% combinations of m elements out of a set of
% n elements.  The binary numbers occur in x
% in ascending order.
% RAS - 3/17/05

% Check on n and m
if n~=floor(n)|m~=floor(m)|m<0|m>n
 error('Improper arguments')
end

np1 = n + 1; mp1 = m + 1;
t = [1 zeros(1,n)];
for i = 1:n  % Generate Pascal's triangle
 t = t + [0 t(1:n)];
end
nCm = t(mp1); % Obtain the number of combinations
x = zeros(nCm,n);  % Allocate space for x
if n==0, return, end % Quit early if n==0
y = [1 zeros(1,n-m) ones(1,m)]; % Start with ones on the right
for i = 1:nCm  % Loop once for each combination
 x(i,:) = y(2:np1); % Add next row
 t = find(y); n1 = t(mp1); % Find rightmost one
 t = find([1 ~y(2:n1-1)]); n0 = t(n1-m); % Find next left zero
 y = [y(1:n0-1) 1 0 y(n1+1:np1) y(n0+2:n1)]; % Prepare next row
end
%----------------

(Remove "xyzzy" and ".invalid" to send me email.)
Roger Stafford

P� Thu, 17 Mar 2005 11:21:26 -0500, skrev Steve Amphlett  
<Firstname.Lastname@where_I_work.com>:

> Antonios wrote:
>>
>>
> <snip, ones and zeros problem...
>
> Another solution, not using dec2bin:
>
>>> n=3;
>>> m=2;
>>> unique(perms([ones(1,m),zeros(1,n-m)]),'rows')
>
> ans =
>
>      0 1 1
>      1 0 1
>      1 1 0

I also had gave perms a go, but as stated in the help text: "for N=11, the  
output takes over 3 giga-bytes". And if n is that small, the looping can't  
take too long.

I think perms should have 'unique' as an input..

-- 
K