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...?

Answer by lvn
on 16 Apr 2014

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

Sign in to comment.

Answer by Alberto
on 12 Apr 2014

Edited by Alberto
on 15 Apr 2014

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

Alberto
on 14 Apr 2014

The idea is implemented, but of course can be coded better.

OP?

Maria
on 15 Apr 2014

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
on 15 Apr 2014

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.

Sign in to comment.

Answer by Image Analyst
on 13 Apr 2014

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.

lvn
on 15 Apr 2014

Image Analyst
on 16 Apr 2014

Maria
on 16 Apr 2014

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.

Sign in to comment.

Opportunities for recent engineering grads.

Apply Today
## 11 Comments

## Image Analyst (view profile)

Direct link to this comment:https://it.mathworks.com/matlabcentral/answers/125528-how-to-sort-rows-of-a-2d-array-such-that-all-elements-along-a-diagonal-are-non-zero#comment_207701

## Jan (view profile)

Direct link to this comment:https://it.mathworks.com/matlabcentral/answers/125528-how-to-sort-rows-of-a-2d-array-such-that-all-elements-along-a-diagonal-are-non-zero#comment_207721

## dpb (view profile)

Direct link to this comment:https://it.mathworks.com/matlabcentral/answers/125528-how-to-sort-rows-of-a-2d-array-such-that-all-elements-along-a-diagonal-are-non-zero#comment_207729

## Maria (view profile)

Direct link to this comment:https://it.mathworks.com/matlabcentral/answers/125528-how-to-sort-rows-of-a-2d-array-such-that-all-elements-along-a-diagonal-are-non-zero#comment_207812

## Image Analyst (view profile)

Direct link to this comment:https://it.mathworks.com/matlabcentral/answers/125528-how-to-sort-rows-of-a-2d-array-such-that-all-elements-along-a-diagonal-are-non-zero#comment_207817

## dpb (view profile)

Direct link to this comment:https://it.mathworks.com/matlabcentral/answers/125528-how-to-sort-rows-of-a-2d-array-such-that-all-elements-along-a-diagonal-are-non-zero#comment_207843

## Maria (view profile)

Direct link to this comment:https://it.mathworks.com/matlabcentral/answers/125528-how-to-sort-rows-of-a-2d-array-such-that-all-elements-along-a-diagonal-are-non-zero#comment_207855

## Image Analyst (view profile)

Direct link to this comment:https://it.mathworks.com/matlabcentral/answers/125528-how-to-sort-rows-of-a-2d-array-such-that-all-elements-along-a-diagonal-are-non-zero#comment_207861

## Maria (view profile)

Direct link to this comment:https://it.mathworks.com/matlabcentral/answers/125528-how-to-sort-rows-of-a-2d-array-such-that-all-elements-along-a-diagonal-are-non-zero#comment_207869

## Image Analyst (view profile)

Direct link to this comment:https://it.mathworks.com/matlabcentral/answers/125528-how-to-sort-rows-of-a-2d-array-such-that-all-elements-along-a-diagonal-are-non-zero#comment_207879

## Alberto (view profile)

Direct link to this comment:https://it.mathworks.com/matlabcentral/answers/125528-how-to-sort-rows-of-a-2d-array-such-that-all-elements-along-a-diagonal-are-non-zero#comment_207991

Sign in to comment.