sorting a matrix to circularly shifted matrix in efficient way
2 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
fatema hamodi
le 3 Avr 2018
Commenté : fatema hamodi
le 4 Avr 2018
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
4 commentaires
Guillaume
le 3 Avr 2018
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.
Réponse acceptée
Guillaume
le 3 Avr 2018
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.
3 commentaires
Guillaume
le 4 Avr 2018
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.
Plus de réponses (1)
John D'Errico
le 3 Avr 2018
Modifié(e) : John D'Errico
le 3 Avr 2018
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.
3 commentaires
John D'Errico
le 3 Avr 2018
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.
Voir également
Catégories
En savoir plus sur Matrices and Arrays dans Help Center et File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!