Pair a row index with a column index

Question

Georgios Pyrgiotakis 2019-7-19

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/472512-pair-a-row-index-with-a-column-index

评论： Jon 2019-7-24

Here is my problem:

I created a matrix that has N number of rows and M columns. No I want to match the n-th row with the m-th coumn but each row_index can have only one coumn_index as a match. Here is how the matrix looks like:

     |  1     2       3       4       5       6       7       8       9       10
-----|-----------------------------------------------------------------------------
  |  8	9	1	6	4	19	12	9	3	1    
  |  20	21	11	18	16	31	NaN	21	15	NaN
  |  NaN	NaN	NaN	NaN	NaN	NaN	NaN	NaN	14	NaN
  |  11	12	2	9	7	22	NaN	12	6	NaN
  |  11	12	2	9	7	22	9	12	6	4
  |  8	9	1	6	4	19	12	9	3	1
  |  8	9	1	6	4	19	12	9	3	1
  |  14	15	5	12	10	25	6	15	9	7
  |  4	5	5	2	0	15	16	5	1	3
 |  4	5	5	2	0	15	16	5	1	3

For instance row index 3 has only one match with column index 9, but row 1 can be match with all coumns. I want to do this matching with the following rule:

Each column can have only one row match

The final result should be something like this :

Row_Index    Column_Index
              7      
              8
              9
              6
              5
              4
              2
              1
              3
             10

I have no idea where to start.

Thank you for your help!

6 个评论
显示 4更早的评论隐藏 4更早的评论

Joel Handy 2019-7-19

So doesnt every row match with every column unless it has a NaN?

Georgios Pyrgiotakis 2019-7-19

Yes. Exactly. But it once a row-colum pair is made you can't reuse any of the two.

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Jon 2019-7-19

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/472512-pair-a-row-index-with-a-column-index#answer_384006

编辑：Jon 2019-7-22

在 MATLAB Online 中打开

This can be categorized as a Matching problem. In particular it can be mapped to a Matching problem on a Bipartite Graph. Let's call your matrix A. Then we consider a graph where one set of nodes are the row numbers and the other set of nodes are the column numbers in A. An edge in this graph connects the node for the ith row with the node for the jth column if there is a column element in the ith row and jth column of your matrix. We are interested in finding a largest cardinality matching (most matching edges) between the row and the columns.

There is a MATLAB File Exchange submission https://www.mathworks.com/matlabcentral/fileexchange/23159-maximum-cardinality-matching that claims to solve exactly this problem (actually it solves a more general problem and is not limited to Bipartite Graphs, but it will work for them as a specicial case, could be other programs out there that would be more efficient for just solving Bipartite Matching problems, but this one will work). Here is some code that shows how you could map your original problem into a matching problem on a Bipartite graph, and then applies the FEX submission to solve the problem. Most thanks go to the authors of the FEX submission where the hard work is done. This is the only experience I have using this FEX submission, as usual you would have to verify that it works properly to solve your problem, but it seemed to work OK for this one example, so that's encouraging.

A = [...
8	9	1	6	4	19	12	9	3	1
20	21	11	18	16	31	NaN	21	15	NaN
NaN	NaN	NaN	NaN	NaN	NaN	NaN	NaN	14	NaN
11	12	2	9	7	22	NaN	12	6	NaN
11	12	2	9	7	22	9	12	6	4
8	9	1	6	4	19	12	9	3	1
8	9	1	6	4	19	12	9	3	1
14	15	5	12	10	25	6	15	9	7
4	5	5	2	0	15	16	5	1	3
4	5	5	2	0	15	16	5	1	3];
% determine dimensions of matrix
[numRows,numCols] = size(A); 
assert(numRows == numCols,'matrix must be square'); % make sure matrix is square
N = numRows; %number of rows and columns
% loop through rows determining if they have any common elements (ignoring
% NaN)with each column, record results in matrix whose i,j element is 1 if
% row i has any elements in common with row j, and otherwise is zero
adj = zeros(N);
for iRow = 1:N
    for jCol = 1:N
        % use set intersection to determine if they have any elements in
        % column, if they do intersection is nonempty
        adj(iRow,jCol) = ~isempty(intersect(A(iRow,:),A(:,jCol)));
    end
end
% consider as Bipartite Graph Matching Problem
% define graph with 2*N nodes, nodes 1 to N represent the rows
% nodes N+1 to 2*N represent the columns
% there is an edge in the graph from node i to node j if row i and column j
% have elements in column.
% define symmetric adjaceny matrix (edges are not directed)
Adj = [zeros(N) adj;adj' zeros(N)]
% use MATLAB fex (File Exchange) submission https://www.mathworks.com/matlabcentral/fileexchange/23159-maximum-cardinality-matching
% to solve
[match] = card_match(Adj);
% we are only interested in the first N elements of match, these tell us
% connections from rows to columns
match = match(1:N);
% since in the graph the node numbers for the columns go from N+1 to 2N we
% subtract of N to get back the associated column numbers
match = match - N;
% display the result
% the match(i) = j means that row i can be matched with column j
disp(match)

9 个评论
显示 7更早的评论隐藏 7更早的评论

Jon 2019-7-24

matchrc3.m

The approach I used to generate the adjacency matrix was a little more general, so depending on your situation it might be applied more broadly, but for your special situation I agree the ith row will match the jth column unless the i,j element is NaN. So you could generate the adjacency matrix with your alternative formulation.

I'm still puzzled however how you ever got that example where the third row matched to column 10.

I have attached my test code. Note it executes 100,000 times. So far I haven't seen a single case where we don't match row 3 either to column 9 or column1.

Maybe you can compare my code to yours to see if you see any differences.

Jon 2019-7-24

Actually, depending upon how you define a valid matching, your method for generating the adjacency matrix may not be correct.

I assumed by a valid match you meant that the ith row and jth column were a valid match if they had any elements in common. So with this definition row 3 is a valid match with column 1 as they have 14 as a common element.

If this is also your definition, then your approach for generating the adjaceny matrix is not correct. It will find that row 3 column 1 of A is NaN and set the adjacency matrix element to zero.

请先登录，再进行评论。