sorting a matrix to circularly shifted matrix in efficient way
2 次查看(过去 30 天)
显示 更早的评论
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 个评论
Guillaume
2018-4-3
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.
采纳的回答
Guillaume
2018-4-3
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 个评论
Guillaume
2018-4-4
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.
更多回答(1 个)
John D'Errico
2018-4-3
编辑:John D'Errico
2018-4-3
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 个评论
John D'Errico
2018-4-3
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.
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Matrices and Arrays 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!