sorting a matrix to circularly shifted matrix in efficient way

hi all

I want to sort a matrix to circularly shifted matrix for example

for input

input=[2,0,0;1,1,0;0,2,0;1,0,1;0,1,1;0,0,2] 
output =[2,0,0,1;0,2,0,3;0,0,2,6;1,1,0,2;0,1,1,5;1,0,1,4]

the last number of each row in the output contain the number of this row in the original matrix

I want to sort very large matrices and my code works fine but it takes a lot of time so I want to know if there is a much faster way to do it I will be so happy if anyone can helps

my code :

% given input  
 function sorted_mat= sort_mat(mat)
[m,n] = size(mat);
sorted_mat=zeros(m,n+1);
count=1;
num_diff_circs=m/n; %consider each shifted array is collection , this is the number of all the collection this is always true  
for n=1:num_diff_circs   
initial_vector=mat(1,1:n);
vector=initial_vector;
order_in_mat =Order(vector);%this function given vector [2,0,0] for example it gives it's order you can use it 
sorted_mat(count,1:n)=vector;
sorted_mat(count,end)=order_in_mat;
num_first_collection=count ;%gives the number of the first vector in collection( collection means the collection 
resulted from shifitng a vector)  in the sorted mat
while(true)
    count=count+1;
 vector=circshift(vector(1,1:n),[0 1]);
  if (~isequal(initial_vector,vector))
    order_in_mat=Order(vector);
    sorted_mat(count,1:num_of_sites)=vector;
    sorted_mat(count,end)=order_in_mat;
  else 
           break;
  end 
end
  rows_out=sorted_mat(num_first_collection:count-1,end);
   [~,~,ib] = intersect(rows_out,mat(:,end), 'stable');
 mat((ib),:)=[];
  % filter out the vector already exist in the sorted matrix from the old
  % matrix )
end
end

[Guillaume]

Am I correct that your code assumes that the inital matrix contains all circularly shifted combinations of the initial vectors and that if the matrix doesn't then it either errors (probably with a subscript out of range error) or produces something meaningless?

If that is the case, then wouldn't it be simpler to just pass the initial vectors (in your example [2 0 0; 1 1 0] and generate the desired matrix rather than starting with a wrongly ordered matrix. Presumably, whatever generated that wrongly ordered matrix still has the initial vectors around?

[fatema hamodi]

I have to sort the matrix to collections (each collection contain the vectors resulted from circularly shifting a vector ) but the first vector of each collection should be the first one in the original matrix after removing from it the vectors that were sorted , that's why I choose to build the new matrix by sorting the original one , do you have better suggestion?

[Guillaume]

Yes, I understand what your code is doing but it seems to me that rather than fixing things after the fact it would be better to generate the right matrix right from the start.

Presumably, at some point your code started with the vectors [2 0 0] and [1 1 0] and then generated that wrongly ordered matrix. Wouldn't it be better to write a function that generates the correct matrix rather than concentrating on fixing a wrongly ordered matrix?

If not, then yes, we can look at optimising your current code.

[fatema hamodi]

I understand . but the problem is, that I have no idea what is the initial vector of each collection . what I know about the initial vector of each collection that it should be the first one appeared in the original matrix after removing the collections that's already had been sorted so the order in which the vectors appears in the original matrix is important that's why I start from it . for very large matrices this code works very slowly I would be so happy if you could help . thanks

Answer 1

[Guillaume]

function [sorted, order] = sort_mat(mat)
   tosort = mat;
   sorted = zeros(size(mat), 'like', mat);
   numelems = size(mat, 2);
   circmat = toeplitz([1, numelems:-1:2], 1:numelems);
   insertrow = 1;
   while ~isempty(tosort)
       circvec = tosort(1, :);
       allperms = circvec(circmat);
       sorted(insertrow:insertrow+numelems-1, :) = allperms;
       tosort = setdiff(tosort, allperms, 'rows', 'stable');
       insertrow = insertrow + numelems;
   end
   if nargout > 1
       [~, order] = ismember(sorted, mat, 'rows');
   end
end

See if it's any faster than your current code. I suspect the slowest part of my code is the setdiff and the shrinking of tosort. That last one could possibly be replaced by some logical indexing.

I've separated the sorted matrix, from the order vector. The latter is only calculated if required as that's probably a bit slow as well.

[fatema hamodi]

thanks a lot it works fine still not quit efficient , I am trying to build the new matrix the way you said at the beginning, by extracting the vectors from the old matrix and supplying them as input to build the new matrix , but how this can be done

[Guillaume]

You need to clarify if there is the possibility that the initial vectors can have (non-circular) permutations of the exact same set of numbers. If that is the case, then as I commented in John's answer I don't think that there is a way to find the initial vectors other than recursively removing all the circular permutations of an identified vector, as you and I have done.

If you cannot have two initial vectors that are permmutations of each other, then John's method of using unique(sort(...), 'rows') is fine.

[fatema hamodi]

there could be a lot of permutations of the exact same set of numbers I can't use John's method

Answer 2

[John D'Errico]

Reduce the input matrix to TWO vectors. [2 0 0] and [1 1 0], or however many are required. Thus...

[U,I] = unique(sort(input,2,'descend'),'rows')
U =
   1     1     0
   2     0     0

I =
   2
   1

So we can go back to input using I.

input(I,:)
ans =
   1     1     0
   2     0     0

Next, take each of those rows, and generate a circularly shifted matrix. (Not that hard. Really.)

[nu,nc] = size(U);
circshiftind = mod(nc-1 + (nc:-1:1)' + (1:nc),nc) + 1;
output = zeros(nu*nc,nc);
L = 0;
for i = 1:size(U,1)
  V_i = input(I(i),:);
  V = V_i(circshiftind);
  output(L+(1:nc),:) = V;
  L = L + nc;
end

% finally, recover the original rows of input
[~,K] = ismember(output,input,'rows');
output = [output,K];

The result being

input
input =
     2     0     0
     1     1     0
     0     2     0
     1     0     1
     0     1     1
     0     0     2

output
output =
     1     1     0     2
     0     1     1     5
     1     0     1     4
     2     0     0     1
     0     2     0     3
     0     0     2     6

And it will be quite efficient.

[Guillaume]

The danger with unique(sort(input,2,'descend'),'rows') is that, for example, it will identify the two input vectors [1 0 1 0] and [1 1 0 0] as circular shifts of the same vector when they aren't.

I'm not sure there's an easy way to easily identify the input vectors other than removing all the circular permutations of a vector once one has been identified and starting again.

[John D'Errico]

This is true. I guess we don't know enough about what to expect. Is the pair of vectors you supply a possibility? You would know if this problem is happening because the output array would be the wrong size. Then remove the rows of input.

[fatema hamodi]

thanks a lot , but as Guillaume said using unique will be danger , if the order in which the collections appears doesn't important , is there a way in which I can extract the vectors as you did without missing collections