Thread Subject: All possible combinations of k features

I am involved in a feature selection project and I have a problem that I hope someone can give me a hand with.

I am trying to generate a matrix that lists all possible combinations of k features out of n possibilities. So for example if n=5 and k = 2 then the resulting matrix would look like this.
0 0 0 1 1
0 0 1 0 1
0 0 1 1 0
0 1 0 0 1
0 1 0 1 0
0 1 1 0 0
1 0 0 0 1
1 0 0 1 0
1 0 1 0 0
1 1 0 0 0

The code I am currently using to do this is:
function idx = apc_mat(n,k)
    idx = [];
    i = 1;
    cont = true;
    while cont
        i_bin = dec2bin(i,n);
        i_mat = i_bin =='1';
        if sum(i_mat) == k;
            idx = [idx;i_mat];
        end
        
        if i>2^n-1
            cont = false;
        else
            i = i+1;
        end
    end
end

The trouble is that this 'top down' approach is unusable for n much more than about 20 or 30. However the end result of something like (100,2) would be a matrix with 100 columns and (100^2-100)/2 rows = 4950 rows which is evaluable. The trouble is I can't get there because my method throws away too much data.

What I am wondering is if there is a 'bottom up' approach that will build the matrix more directly and this allow larger problems to be solved.

Thanks in advance for any help.

"Brian MacDonald" wrote in message <jcagp4$2dg$1@newscl01ah.mathworks.com>...
> I am trying to generate a matrix that lists all possible combinations of k features out of n possibilities. So for example if n=5 and k = 2 then the resulting matrix would look like this.
> 0 0 0 1 1
> 0 0 1 0 1
> 0 0 1 1 0
> 0 1 0 0 1
> 0 1 0 1 0
> 0 1 1 0 0
> 1 0 0 0 1
> 1 0 0 1 0
> 1 0 1 0 0
> 1 1 0 0 0
- - - - - - - - - - -
  The function 'nchoosek' is what you need.

Roger Stafford

"Roger Stafford" wrote in message <jcajms$ce5$1@newscl01ah.mathworks.com>...
> "Brian MacDonald" wrote in message <jcagp4$2dg$1@newscl01ah.mathworks.com>...
> > I am trying to generate a matrix that lists all possible combinations of k features out of n possibilities. So for example if n=5 and k = 2 then the resulting matrix would look like this.
> > 0 0 0 1 1
> > 0 0 1 0 1
> > 0 0 1 1 0
> > 0 1 0 0 1
> > 0 1 0 1 0
> > 0 1 1 0 0
> > 1 0 0 0 1
> > 1 0 0 1 0
> > 1 0 1 0 0
> > 1 1 0 0 0
> - - - - - - - - - - -
> The function 'nchoosek' is what you need.
>
> Roger Stafford


Thank you. That worked perfectly...and fast.