Rearranging rows of a boolean matrix so that the diagonals are all non-zero if possible

15 次查看（过去 30 天）
2Lindsay2
2Lindsay2 2020-7-10
编辑： Matt J 2020-7-18
Hello, just as a disclaimer I have a question about improving my code, not on how to get it to work.
I wrote a code that rearranges just the rows of a boolean matrix so that the diagonal values are all non-zero. This code gets pretty slow as the matrix being fed in gets pretty large. It starts lagging pretty bad with 25x25 matrices. I'm curious what I can do to speed my code up.
Here is the function that I have right now:
function [reAdmis, unmatchedTaskList] = rearrange(admis)
[n,~] = size(admis);
potAssignment = zeros(1,n);%potential assignments
dList=1:n; %Decision list: elements are zeroed if chosen
reAdmis = zeros(n,n); % reAdmis will be the answer
AdmisTemp = admis;
CC = sum(admis,1); %column count
RC = sum(admis,2); %row count
[~, colIndex] = sort(CC);
[~, rowIndex] = sort(RC);
[reAdmisTemp, dIndex] = reorganizeRow(AdmisTemp, rowIndex, n); %reorganizes the rows based on RC
for i = 1:n
for j = 1:n
if reAdmisTemp(j,colIndex(i))
reAdmis(colIndex(i),:)=admis(rowIndex(j),:);
AdmisTemp(rowIndex(j),:)=zeros; %used row gets zeroed
dList(dIndex(j))=0; % chosen element in dList is zeroed
potAssignment(dIndex(j))=colIndex(i); %Potential assignment is updated
AdmisTemp(:,colIndex(i))=zeros; %used column gets zeroed
break
end
end
CC = sum(AdmisTemp,1);
RC = sum(AdmisTemp,2);
[~, colIndex] = sort(CC);
[~, rowIndex] = sort(RC);
[reAdmisTemp, dIndex] = reorganizeRow(AdmisTemp, rowIndex, n);
end
end
function [organized, dIndex] = reorganizeRow(A, dIndex, n)
organized = zeros(n,n);
for i = 1:n
organized(i,:)=A(dIndex(i),:);
end
end
An example boolean matrix to use and its output could be:
admis = [1 0 1 0 0
0 0 0 0 1
1 1 0 0 1
0 1 0 1 1
1 1 1 1 1]
reAdmis = [1 1 0 0 1
0 1 0 1 1
1 0 1 0 0
1 1 1 1 1
0 0 0 0 1]
My hope is that this can be as fast as possible. I have no hard number for a time requirement, however my clocked speed using tic-toc was about 0.0003 seconds, which I'd like to be able to beat.
Thank you in advance for any help that you are able to provide
  4 个评论
显示 2更早的评论
Matt J
Matt J 2020-7-16
编辑：Matt J 2020-7-16
Yes, but how large are you hoping to make the matrix? Would it get much larger than 25x25?

请先登录，再进行评论。

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

回答（2 个）

Bruno Luong
Bruno Luong 2020-7-16
Your problem belong to the so-called "Assignment problem", that has dedicated algorithm called Hungarian assigment.
Take a look on the formal definition, try to understand it then find some implementation on File Exchange.
  6 个评论
显示 4更早的评论

请先登录，再进行评论。

Matt J
Matt J 2020-7-11
When your version works, it often works faster than the version below, however your version doesn't always get it right. I've attached a .mat file with an example matrix admis for which your version does not manage to get all non-zero diagonal elements.
load admis700 admis
N=size(admis,1);
P=optimvar('P',[N,N],'LowerBound',0,'UpperBound',1,'Type','integer');
prob=optimproblem('ObjectiveSense','max');
prob.Constraints.row=sum(P,1)==ones(1,N);
prob.Constraints.col=sum(P,2)==ones(N,1);
E=speye(N);
opts=optimoptions('intlinprog','Display','none');
tic;
prob.Objective=sum(sum((P*admis).*E));
sol=solve(prob,'options',opts);
reAdmis=round(sol.P)*admis;
toc;
  6 个评论
显示 4更早的评论
2Lindsay2
2Lindsay2 2020-7-18
Thank you! I notice though that there is no guarantee that the sparse matrix that gets produced actually has a solution where all the diagonal elements are one. When there is not a solution where all the diagonal elements are one my code stops inserting the rows into the empty matrix "reAdmis", which is why the results would be different. When you tested this did you verify there was a solution where all the diagonal elements were one?
Matt J
Matt J 2020-7-18
编辑：Matt J 2020-7-18
The randomization procedure that I used to explore different choices of admis did not ensure this, however, the example failure cases admis10.mat and admis700.mat that I provided for you did have solutions where all the diagonal elements are one, as you will see when you run either my code or Bruno's.
In any case, I do not think there is any longer any reason for you to focus on either my solution or your own. Bruno's solution works and, for large N, is the fastest among all 3 methods. To demonstrate, I attach a 3rd data example, for which your solution does happen to work:
load admis200
tic;
R1=Lindsay(admis);
toc;
tic
R2=MattJ(admis);
toc
tic
R3=Bruno(admis);
toc
Tr1=trace(R1)
Tr2=trace(R2)
Tr3=trace(R3)
results in
Elapsed time is 0.030986 seconds.
Elapsed time is 0.135317 seconds.
Elapsed time is 0.015373 seconds.
Tr1 =
200
Tr2 =
200
Tr3 =
200

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Operating on Diagonal Matrices 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by