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

### Ano (view profile)

on 18 Mar 2016
Latest activity Edited by Roger Stafford

on 24 Mar 2016

### Roger Stafford (view profile)

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!

### Roger Stafford (view profile)

on 18 Mar 2016

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

### Ano (view profile)

on 18 Mar 2016
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

### Ano (view profile)

on 24 Mar 2016
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

### Roger Stafford (view profile)

on 24 Mar 2016
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.

### Guillaume (view profile)

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]

Ano

### Ano (view profile)

on 18 Mar 2016
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

### Guillaume (view profile)

on 18 Mar 2016
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.