Asked by Ano
on 18 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!

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)));

end

[~,b] = max(q);

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

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

Roger Stafford
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.

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]

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

Sign in to comment.

Opportunities for recent engineering grads.

Apply Today
## 0 Comments

Sign in to comment.