MATLAB: Combinations of a matrix…..

combinatorics

I am trying to find an command/algorithm which gives me all possible translates of a given matrix that has fixed #a,#b, and #c. By translates I mean all those matrices which have the same #a,#b, and #c but different locations for these elements .

For example

M=[3 3 3;1 2 3;1 2 3]

the answer would be something like

M1=[1 2 3;1 2 3;3 3 3]
M2=[1 1 3;2 2 3;3 3 3]....

I dont know if its possible for matrices or not. Should I think of matrix as an array and try to find combinations for that array.

If there exists such an algorithm then kindly name it so that I can look into its theory

Best Answer

If I understand you correctly, your problem is the same whether your M is a matrix or a single vector with the same total number of elements, so for convenience I will assume you really wish to fill a row vector with your three numbers in all possible combinations. If there are to be na, nb, and nc counts of the three quantities a, b, and c respectively, taken in all possible combinations, then the total number of these combinations would be (na+nb+nc)!/na!/nb!/nc!. Our task is therefore to generate a single matrix M with that many rows and na+nb+nc columns where each row is one of the possible combinations. (You should be cautious about how large you make these counts. The total number of combinations can be a surprisingly large number.)

We can do this with two calls on matlab's 'nchoosek' function, and we will take advantage of the fact that

 (na+nb+nc)!/na!/nb!/nc! = (na+nb+nc)!/na!/(nb+nc)! * (nb+nc)!/nb!/nc!

which as you see is the product of two particular 'nchoosek' combination count numbers.

The following matlab code should accomplish this goal. (There is probably a more efficient way of generating this but I am too lazy at the moment to work it out.)

 C1 = nchoosek(1:na+nb+nc,na); % Here are the two calls on 'nchoosek'
 C2 = nchoosek(1:nb+nc,nb);
 M = c*ones(size(C1,1)*size(C2,1),na+nb+nc); % First, fill M with all c's
 k1 = 0;
 for k2 = 1:size(C1,1)
   p1 = C1(k2,:); % Use C1 to generate indices for inserting a's
   q1 = 1:na+nb+nc;
   q1(p1) = [];  % These indices will point to b and c locations
   for k3 = 1:size(C2,1)
     p2 = C2(k3,:); % Use C2 to generate indices for inserting b's
     k1 = k1 + 1; % Advance the row index of M
     M(k1,p1) = a; % Insert na a's
     M(k1,q1(p2)) = b; % and nb b's
   end
 end

Related Solutions

MATLAB: Alternative to blkdiag and mat2cell functions

You could consider using sparse() to put the matrix together. It is designed to take vectors of row coordinates and corresponding column coordinates and corresponding values, and assemble them into a matrix. You could then full() if you need to.

The difficulty you are encountering is that when you index on multiple non-scalar indices, then MATLAB does not use "corresponding" elements. Instead, MATLAB uses all possible combinations of indices.

M([1 2], [3 4]) = 5

would assign to M(1,3), M(2,3), M(1,4), M(2,4)

MATLAB does not have a syntax for "corresponding" index assignment. Instead what you need to do is use a method of converting the corresponding indices into linear indices and assign to there. The function designed to work convert corresponding indices into linear indices is sub2ind().

There are occasions on which it pays to skip using sub2ind() and instead use the mathematical transformations involved -- especially if you are doing several cases of assigning to sub-arrays of consistent sizes and spatial relationship. For example, if you have the linear indices IDX for a block at (R,C) and want to address something further down the diagonal, then

new_IDX = IDX + CD*number_of_rows + RD

where CD is difference in columns and RD is difference in rows .

MATLAB: How to create a matrix out of all the possible combinations of a vector

Please see answer by Roger Stafford.

In your case:

a = 3:5;
v = [0,-1,1];
n = cumsum(a,'reverse');
C1 = nchoosek(1:n(1),a(1)); % Here are the two calls on 'nchoosek'
C2 = nchoosek(1:n(2),a(2));
M = ones(size(C1,1)*size(C2,1),n(1)); % First, fill M with all 1's
k1 = 0;
for k2 = 1:size(C1,1)
    p1 = C1(k2,:); % Use C1 to generate indices for inserting 0's
    q1 = 1:n(1);
    q1(p1) = [];  % These indices will point to -1 and 1 locations
    for k3 = 1:size(C2,1)
        p2 = C2(k3,:); % Use C2 to generate indices for inserting -1's
        k1 = k1 + 1; % Advance the row index of M
        M(k1,p1) = v(1); % Insert  0's
        M(k1,q1(p2)) = v(2); % and  -1's
    end
end

Best Answer

Related Solutions

MATLAB: Alternative to blkdiag and mat2cell functions

MATLAB: How to create a matrix out of all the possible combinations of a vector

Related Question