How to sort rows of a 2D array, such that all elements along a diagonal are non-zero?

15 次查看（过去 30 天）
Maria
Maria 2014-4-12
回答： lvn 2014-4-16
Thank you for looking at my question.
The problem: I have a square matrix containing random 0s and 1s, and I need to swap the rows around, so that all elements along one of the diagonals are 1s. (every row and column contains at least one 1, to make sure this is possible)
Is there any function that will be able to do this automatically or can you suggest how to go about doing it with code...?
  11 个评论
显示 9更早的评论
Image Analyst
Image Analyst 2014-4-13
I think this might be one of those problems that looks deceptively easy at first but once you get into it, it is revealed to be a lot harder, kind of like the knapsack problem or the traveling salesman problem.
Alberto
Alberto 2014-4-14
I will comment my answer (somebody has to).
You can prove by induction that the property of 'having a 1 in each row and each column' can be transformed in the desired way (really easy prof, i promise).
So you have to cross the matrix, looking in every step k a row :
1) with an element 1 in the k-th and
2) the remaining matrix has the same property I talked before.
It will return how the matrix's rows has to be reordered.

请先登录，再进行评论。

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

回答（3 个）

lvn
lvn 2014-4-16
For reference, here is a solution using the backtracking. The main algorithm part is around 20 lines.
This is the initial solution
xoriginal =
1 1 0 0 1
1 1 0 0 1
0 0 1 0 0
0 1 1 1 0
0 1 0 0 1
Shuffled version
x =
0 0 1 0 0
0 1 0 0 1
1 1 0 0 1
1 1 0 0 1
0 1 1 1 0
This is the solution found
xsol =
1 1 0 0 1
0 1 0 0 1
0 0 1 0 0
0 1 1 1 0
1 1 0 0 1
Order of the rows:
per =
3 2 1 5 4
Code:
function answw2
n=5 ; %Generate a matrix that fulfills the requirements
xoriginal=diag(ones(n,1));
y=rand(n,n);
xoriginal(y<(n/2-1)/(n-1))=1; %so that on average as much 0's as 1's (so sum(x(:))/n^2 = 0.5 on average)
x=xoriginal(randperm(n),:); %And permute it so that we have a challenge
%Alternatively use x=round(rand(n,n)) for a random 1/0 matrix with no guaranteed solution
%Now put the rows with fewest 1's on top, as it is best to start with these
[~,isorted]=sort(sum(x,2));
x=x(isorted,:);
%And now find the solution
per=first(x,0,1:n);
%Output the solution
disp('This is the initial solution'); xoriginal
disp('Shuffled version'); x
if ~isnan(per)
disp('This is the solution found'); xsol(per,:)=x
disp('Order of the rows: '); per
assert(all(diag(xsol)==1)) %Sanity test
else
disp('No solution found !');
return
end;
end
function solution=first(X, row, whichrowstoplace) %For a single root, loop over all leaves
solution=[];
for nr=1:length(X)-row %Try all possibilities to place the row + 1 in the correct position
solution=next(X, row+1, nr, whichrowstoplace);
if ~isnan(solution) %We got ourselves a solution, we can go back up a level
return
end
end
end
function solution=next(X, row, nr, whichrowstoplace)
firstrow=X(row,:); %Take the row
onelocation=find(firstrow); %And find the location of the ones
leaves=onelocation(ismember(onelocation,whichrowstoplace)); %We are only interested in the ones that we still need
if nr>length(leaves) %You exhausted all possible tests, the row cannot be placed and therefore root must be bad
solution=NaN;
else %Otherwise leaves(nr) is the next (candidate) solution
solution=[leaves(nr) first(X, row, whichrowstoplace(whichrowstoplace~=leaves(nr)))];
end;
end
Alberto
Alberto 2014-4-12
编辑：Alberto 2014-4-15
I created the function check(A), so i can check if the property 'every row and column are not all zeros'. Its useful later:
function condition=check(A)
cf=zeros(1,length(A));
for k=1:length(A) if sum(find(A(k,:)))==0 sum(find(A(:,k)))==0 cf(k)=0;
else
cf(k)=1;
end
end
if sum(cf)==length(A) condition=1;
else condition=0; end
end
Now you have a matrix A, use this script:
rowspermute=zeros(1,length(A));
B=A
mirango=1:length(A)
for k=1:length(A) % kth column
for j=mirango
miraux=mirango;
miraux(find(mirango==j))=[];
if A(j,k)==1 && check( A(miraux , k+1:end) )
rowspermute(k)=j;
mirango=miraux;
break
end
end
if rowspermute(k)
A(rowspermute(k), :)=zeros(1,length(A));
end
end
rowspermute % has the rows to reorder
  4 个评论
显示 2更早的评论
Maria
Maria 2014-4-15
编辑：Maria 2014-4-15
Could you please explain what these lines of code mean?
if rowspermute(k)
A(rowspermute(k), :)=zeros(1,length(A));
end
Sorry for late comment.
Alberto
Alberto 2014-4-15
The idea behind the code is selecting a row with 1 in the desired position, and that can be eliminated in the matrix without loosing the property (ones in every row and column).
At first i tried to erase the row in the matrix so the same row couldn't be chosen twice, but it was tricky to track which number of the original rows in matrix A.
I thought putting zeroes in that row was an elegant solution to prevent that row to be chosen again.
The if block has the porpose to be sure a row was selected before.

请先登录，再进行评论。

Image Analyst
Image Analyst 2014-4-13
If you're willing to use circshift, then try this:
clc;
rows = 20;
columns = 20;
m = randi(2, [rows, columns])-1
output = zeros(size(m));
for row = 1 : rows
% Get this row.
thisRow = m(row, :);
% Shift it until we get a 1 in column "row".
for colShift = 0 : columns - 1
% Shift this row by some amount.
shiftedRow = circshift(thisRow, colShift, 2)
% See if we shiftwed a 1 into the diagonal element at column "row"
if shiftedRow(row) == 1
% It's a 1, so we're done.
output(row, :) = shiftedRow;
% Quit shifting this row.
break;
end
end
end
output % Display in command window.
  6 个评论
显示 4更早的评论
Image Analyst
Image Analyst 2014-4-16
Good information. I think you're right. Nice to know there's an organized way for solving it. Seems a bit tough for a homework problem though - glad I don't have that teacher. I started thinking about graph solving algorithms and thought it had to be like one of them. Personally I only know about Djikstra and A* though there are lots of similar kinds of graph search algorithms. (Funny, after I had independently "discovered" A* as part of my Ph.D. research, I found out that it had already been invented. Bummer. Lost out on that glory.)
Maria
Maria 2014-4-16
编辑：Maria 2014-4-16
Thank you everyone. I think the question is solved now with the help of my little brother, who figured out a way to get past the circshift problem. I have not finished coding it but will post on here when I'm finished for anyone who's still interested.
The code works by going over each row's diagonal A(i,i) and if theres a 0 in that row's diagonal it proceeds to check whether the elements below that row in the corresponding column (A(i+1:end,i) contain any 1s or if its all 0s. Then for each case there is a different shifting pattern, which ensures that all rows are used and no rows become 'stuck' at the top.
It works on paper with a particularly nasty matrix that my previous code could't rearrange, but it is expected to have 10+ loops....
My original idea was something along the lines of that backtracking algorithm but I had trouble writing the code. As you may have guessed, I only started using Matlab recently and have no previous coding experience.

请先登录，再进行评论。

类别

在 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