Find the best combination of each pair of entries in a matrix

Hello, I would like to find the best combination (max probability)of each (row, column) pair in my probability matrix, such that I shall get at the end each row is associated with only one column , in other words a bijection. here is an example to clarify more the task:

    my_Probability_Matrix =[0.0192 0.0152 0.0246 0.0235; 
                            0.2521 0.0135 0.475 0.0278; 
                            0.0141 0.0175 0.0257 0.106; 
                            0.0226 0.0026 0.0155 0.0165];

and I should get the following combinations: Best_Probabilities(row,column)={(1,2);(2,3);(3,4);(4,1)} any ideas how to implement this without too many iterations?! Thank you!

Answer 1

[Roger Stafford]

The number of possible bijections for an n-by-n matrix, M, would be n factorial. Use 'perms' to generate all possible permutations of 1:n and for each, compute the corresponding product from your matrix.

P = perms(1:n);
q = zeros(size(P,1),1);
for k = 1:size(P,1)
  q(k) = prod(M((1:n)+n*(P(k,:)-1)));
end
[~,b] = max(q);

Your best combination is then P(b,:);

[Ano]

Hello, @ Roger Stafford thank you very much it's working now perfectly.

@ Guillaume, thank you very much for your help, the idea is to choose the pairs with higher probability first and the rest are just attributed to ensure a bijection between rows and columns.

best regards!

[Ano]

Hello @Roger Stafford, would it be possible to give me the reference from where you took the mathematical expression ((1:n)+n*(P(k,:)-1))). thank you, kind regards!

[Roger Stafford]

It's the standard formula used to transform subscripts into linear indices in Matlab. In the case of a two-dimensional matrix, 'M', if 'ix' is the row (first) subscript and 'iy' the column (second) subscript, and if there are 'n' rows, then the corresponding linear index is:

L = ix + n*(iy-1)

The element M(ix,iy) is equally well referenced by just M(L).

In the case of (1:n)+n*(P(k,:)-1) it is an entire vector of subscript pairs that is being transformed into a corresponding vector of linear indices:

[1+n*(P(k,1)-1) , 2+n*(P(k,2)-1) , 3+n*(P(k,3)-1) , ... ]

See

   http://www.mathworks.com/help/matlab/ref/ind2sub.html

and

   http://www.mathworks.com/help/matlab/ref/sub2ind.html

for an explanation of the correspondence between subscripts and linear indices.

Answer 2

[Guillaume]

I'm not sure I've understood your question correctly since for me the highest value in the first row is column 3, but if I have, then:

[~, col] = max(my_Probability_Matrix, [], 2); %position of the max in each row
Best_Probabilities = [(1:size(my_Probability_Matrix, 1))', col]

[Ano]

Thank you very much Guillaume, your code works pretty fast but the pairs that I get have I repeated entry 'column 3 is used twice by row 1 and row 2'

Best_Probabilities =
   1     3
   2     3
   3     4
   4     1

I tried to compare the entries with similar indices, but it still not clear for me how to do the implementation. any ideas ?!

[Guillaume]

Yes, as I said, I don't understand why you've selected (1, 2) for the first pair. Can you explain what the criteria for choosing pairs is.