Pair a row index with a column index

3 次查看(过去 30 天)
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
-----|-----------------------------------------------------------------------------
1 | 8 9 1 6 4 19 12 9 3 1
2 | 20 21 11 18 16 31 NaN 21 15 NaN
3 | NaN NaN NaN NaN NaN NaN NaN NaN 14 NaN
4 | 11 12 2 9 7 22 NaN 12 6 NaN
5 | 11 12 2 9 7 22 9 12 6 4
6 | 8 9 1 6 4 19 12 9 3 1
7 | 8 9 1 6 4 19 12 9 3 1
8 | 14 15 5 12 10 25 6 15 9 7
9 | 4 5 5 2 0 15 16 5 1 3
10 | 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
1 7
2 8
3 9
4 6
5 5
6 4
7 2
8 1
9 3
10 10
I have no idea where to start.
Thank you for your help!
  6 个评论
Joel Handy
Joel Handy 2019-7-19
So doesnt every row match with every column unless it has a NaN?
Georgios Pyrgiotakis
Yes. Exactly. But it once a row-colum pair is made you can't reuse any of the two.

请先登录,再进行评论。

采纳的回答

Jon
Jon 2019-7-19
编辑:Jon 2019-7-22
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 个评论
Jon
Jon 2019-7-24
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
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.

请先登录,再进行评论。

更多回答(0 个)

类别

Help CenterFile Exchange 中查找有关 Interpolation 的更多信息

产品


版本

R2017b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by