MATLAB Answers


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

Asked by Ano
on 18 Mar 2016
Latest activity Edited by Roger Stafford on 24 Mar 2016
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!


Sign in to comment.

2 Answers

Answer by Roger Stafford on 18 Mar 2016
 Accepted Answer

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)));
[~,b] = max(q);
Your best combination is then P(b,:);


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!
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!
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) , ... ]
for an explanation of the correspondence between subscripts and linear indices.

Sign in to comment.

Answer by Guillaume
on 18 Mar 2016

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]


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

Sign in to comment.