http://www.mathworks.com/matlabcentral/newsreader/view_thread/238797
MATLAB Central Newsreader  Check if two shifted matrices are equal
Feed for thread: Check if two shifted matrices are equal
enus
©19942014 by MathWorks, Inc.
webmaster@mathworks.com
MATLAB Central Newsreader
http://blogs.law.harvard.edu/tech/rss
60
MathWorks
http://www.mathworks.com/images/membrane_icon.gif

Thu, 06 Nov 2008 19:59:02 +0000
Check if two shifted matrices are equal
http://www.mathworks.com/matlabcentral/newsreader/view_thread/238797#609439
Colin
Hi all,<br>
<br>
I have two matrices that are 1 x 130943 and contain hex values.<br>
<br>
I want to be able to verify that they are in fact identical matrices but only one is shifted with respect to the other.<br>
<br>
A simple example could be:<br>
<br>
M1 =<br>
a<br>
b<br>
c<br>
d<br>
<br>
M2 =<br>
b<br>
c<br>
d<br>
a<br>
<br>
My first thought was to use the 'circshift' function on one matrix and run it through a loop until the two matrices match exactly. Unfortunately, this takes a very long time.<br>
<br>
Perhaps there is a faster/easier way to accomplish this?<br>
<br>
Thanks for any tips and insight,<br>
czhe

Thu, 06 Nov 2008 21:00:44 +0000
Re: Check if two shifted matrices are equal
http://www.mathworks.com/matlabcentral/newsreader/view_thread/238797#609453
Walter Roberson
Colin wrote:<br>
<br>
> I have two matrices that are 1 x 130943 and contain hex values.<br>
<br>
> I want to be able to verify that they are in fact identical matrices but only one is shifted<br>
> with respect to the other.<br>
<br>
Do you only need to know that they are identical (but perhaps shifted), or do you need to<br>
know the amount of the shift?<br>
<br>
And do you happen to have any constraint on how much shift there would be? For example,<br>
would it just happen to be the case that the shift would be by an even number of positions?<br>
<br>
Is there exactly 1 hex digit per array location?<br>
<br>
Would a fast "Not the same" or "Might be the same" be useful to you? e.g., are the<br>
arrays often different and being the same is the much less common case that you can<br>
afford to take longer to prove? For example, when two arrays are different, then<br>
their histograms would often be different, so if the histograms are different then<br>
you know [relatively quickly] that the arrays are not shifts of each other, and if<br>
the histograms are the same then you could run a more detailed test.<br>
<br>
 <br>
.signature note: I am now avoiding replying to unclear or ambiguous postings.<br>
Please review questions before posting them. Be specific. Use examples of what you mean,<br>
of what you don't mean. Specify boundary conditions, and data classes and value<br>
relationships  what if we scrambled your data or used Inf, NaN, or complex(rand,rand)?

Thu, 06 Nov 2008 21:07:02 +0000
Re: Check if two shifted matrices are equal
http://www.mathworks.com/matlabcentral/newsreader/view_thread/238797#609454
Colin
Walter Roberson <roberson@hushmail.com> wrote in message <vVIQk.3167$dy1.2828@newsfe01.iad>...<br>
> Colin wrote:<br>
> <br>
> > I have two matrices that are 1 x 130943 and contain hex values.<br>
> <br>
> > I want to be able to verify that they are in fact identical matrices but only one is shifted<br>
> > with respect to the other.<br>
> <br>
> Do you only need to know that they are identical (but perhaps shifted), or do you need to<br>
> know the amount of the shift?<br>
> <br>
> And do you happen to have any constraint on how much shift there would be? For example,<br>
> would it just happen to be the case that the shift would be by an even number of positions?<br>
> <br>
> Is there exactly 1 hex digit per array location?<br>
> <br>
> Would a fast "Not the same" or "Might be the same" be useful to you? e.g., are the<br>
> arrays often different and being the same is the much less common case that you can<br>
> afford to take longer to prove? For example, when two arrays are different, then<br>
> their histograms would often be different, so if the histograms are different then<br>
> you know [relatively quickly] that the arrays are not shifts of each other, and if<br>
> the histograms are the same then you could run a more detailed test.<br>
> <br>
>  <br>
> .signature note: I am now avoiding replying to unclear or ambiguous postings.<br>
> Please review questions before posting them. Be specific. Use examples of what you mean,<br>
> of what you don't mean. Specify boundary conditions, and data classes and value<br>
> relationships  what if we scrambled your data or used Inf, NaN, or complex(rand,rand)?<br>
<br>
Hi! Thanks for the quick reply.<br>
<br>
Your suggestions are very helpful. It would definitely be beneficial for me if I could tell right away if the matrices do not match. Could I do this without any manipulation of the matrices themselves?<br>
<br>
If I find that they are indeed matching, I still need to perform the shift so they match exactly, so I suppose I would need to know how much they are shifted by.

Thu, 06 Nov 2008 21:12:01 +0000
Re: Check if two shifted matrices are equal
http://www.mathworks.com/matlabcentral/newsreader/view_thread/238797#609457
Colin
Walter Roberson <roberson@hushmail.com> wrote in message <vVIQk.3167$dy1.2828@newsfe01.iad>...<br>
> Colin wrote:<br>
> <br>
> > I have two matrices that are 1 x 130943 and contain hex values.<br>
> <br>
> > I want to be able to verify that they are in fact identical matrices but only one is shifted<br>
> > with respect to the other.<br>
> <br>
> Do you only need to know that they are identical (but perhaps shifted), or do you need to<br>
> know the amount of the shift?<br>
> <br>
> And do you happen to have any constraint on how much shift there would be? For example,<br>
> would it just happen to be the case that the shift would be by an even number of positions?<br>
> <br>
> Is there exactly 1 hex digit per array location?<br>
> <br>
> Would a fast "Not the same" or "Might be the same" be useful to you? e.g., are the<br>
> arrays often different and being the same is the much less common case that you can<br>
> afford to take longer to prove? For example, when two arrays are different, then<br>
> their histograms would often be different, so if the histograms are different then<br>
> you know [relatively quickly] that the arrays are not shifts of each other, and if<br>
> the histograms are the same then you could run a more detailed test.<br>
> <br>
>  <br>
> .signature note: I am now avoiding replying to unclear or ambiguous postings.<br>
> Please review questions before posting them. Be specific. Use examples of what you mean,<br>
> of what you don't mean. Specify boundary conditions, and data classes and value<br>
> relationships  what if we scrambled your data or used Inf, NaN, or complex(rand,rand)?<br>
<br>
Sorry and to address your other questions, the matrix could be shifted by any arbitrary integer number up to the size of the matrix minus 1.<br>
<br>
There is a hex value at exactly every index.

Thu, 06 Nov 2008 23:16:04 +0000
Re: Check if two shifted matrices are equal
http://www.mathworks.com/matlabcentral/newsreader/view_thread/238797#609487
Roger Stafford
"Colin " <colinzhe@gmail.com> wrote in message <gevia6$2hk$1@fred.mathworks.com>...<br>
> Hi all,<br>
> <br>
> I have two matrices that are 1 x 130943 and contain hex values.<br>
> <br>
> I want to be able to verify that they are in fact identical matrices but only one is shifted with respect to the other.<br>
> <br>
> A simple example could be:<br>
> <br>
> M1 =<br>
> a<br>
> b<br>
> c<br>
> d<br>
> <br>
> M2 =<br>
> b<br>
> c<br>
> d<br>
> a<br>
> <br>
> My first thought was to use the 'circshift' function on one matrix and run it through a loop until the two matrices match exactly. Unfortunately, this takes a very long time.<br>
> <br>
> Perhaps there is a faster/easier way to accomplish this?<br>
> <br>
> Thanks for any tips and insight,<br>
> czhe<br>
<br>
You might consider two nested whileloops in which the outer one moves through possible shift amounts and the inner one does a match one at a time with individual elements shifted by that amount until either a mismatch is found or the entire shifted vectors are found to match. The outer loop would exit either when a total match is found or when all possible shift amounts have been tried without success.<br>
<br>
This would tend to minimize the total number of comparisons that are necessary, and for the large size you are considering that might be important. That is, doing a 'circshift' followed by a vector comparison might well take more time on the average, even though vectorized, than comparing elements one at a time in a whileloop until the first mismatch occurs.<br>
<br>
Roger Stafford

Fri, 07 Nov 2008 00:59:02 +0000
Re: Check if two shifted matrices are equal
http://www.mathworks.com/matlabcentral/newsreader/view_thread/238797#609497
Bruno Luong
"Colin " <colinzhe@gmail.com> wrote in message <gevia6$2hk$1@fred.mathworks.com>...<br>
<br>
> <br>
> Perhaps there is a faster/easier way to accomplish this?<br>
> <br>
<br>
a=[7 0 3 0 1 8 7 3 10 0];<br>
b=[3 0 1 8 7 3 10 0 7 0];<br>
<br>
% Engine<br>
shift=findstr(b,[a a])1<br>
<br>
% Check<br>
n = length(a);<br>
<br>
if isempty(shift)<br>
fprintf('cannot match after circular shift')<br>
else<br>
shift = shift(1);<br>
shiftedidx = mod((1:n)+shift1,length(a))+1;<br>
isequal(b, a(shiftedidx ))<br>
end<br>
<br>
% Bruno

Fri, 07 Nov 2008 09:51:02 +0000
Re: Check if two shifted matrices are equal
http://www.mathworks.com/matlabcentral/newsreader/view_thread/238797#609540
Jos
"Colin " <colinzhe@gmail.com> wrote in message <gevia6$2hk$1@fred.mathworks.com>...<br>
> Hi all,<br>
> <br>
> I have two matrices that are 1 x 130943 and contain hex values.<br>
> <br>
> I want to be able to verify that they are in fact identical matrices but only one is shifted with respect to the other.<br>
> <br>
> A simple example could be:<br>
> <br>
> M1 =<br>
> a<br>
> b<br>
> c<br>
> d<br>
> <br>
> M2 =<br>
> b<br>
> c<br>
> d<br>
> a<br>
> <br>
> My first thought was to use the 'circshift' function on one matrix and run it through a loop until the two matrices match exactly. Unfortunately, this takes a very long time.<br>
> <br>
> Perhaps there is a faster/easier way to accomplish this?<br>
> <br>
> Thanks for any tips and insight,<br>
> czhe<br>
<br>
This is pretty quick:<br>
<br>
%== Start of Code ==<br>
% some data<br>
a = rand(100000,1) ;<br>
% create a shifted vector<br>
nc = ceil(numel(a)*rand) <br>
b = circshift(a,nc) ; % shifted<br>
<br>
% try different types<br>
% b = rand(size(a)) ; % completely different<br>
% b([1 2]) = b([2 1]) ; % swap two elements<br>
% b = a ; % no shift<br>
<br>
[i,i] = ismember(a,b) ;<br>
di = abs(diff(i)) ;<br>
ShiftN =  find(di>1) ; % minus sign!<br>
<br>
AreTheSame = numel(ShiftN)<2 <br>
if AreTheSame,<br>
ShiftN = max([ShiftN ; numel(a) + ShiftN ; 0])<br>
b2 = circshift(a,ShiftN) ;<br>
isequal(b2,b) <br>
end<br>
%== End of Code ==<br>
<br>
hth<br>
Jos

Fri, 07 Nov 2008 15:24:02 +0000
Re: Check if two shifted matrices are equal
http://www.mathworks.com/matlabcentral/newsreader/view_thread/238797#609601
Colin
Thank you all very much! This helps a lot.