MATLAB Central Newsreader - Check if two shifted matrices are equal

Check if two shifted matrices are equal

Colin — Thu, 06 Nov 2008 19:59:02 -0500

Hi all,

I have two matrices that are 1 x 130943 and contain hex values.

I want to be able to verify that they are in fact identical matrices but only one is shifted with respect to the other.

A simple example could be:

M1 =
a
b
c
d

M2 =
b
c
d
a

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.

Perhaps there is a faster/easier way to accomplish this?

Thanks for any tips and insight,
czhe

Re: Check if two shifted matrices are equal

Walter Roberson — Thu, 06 Nov 2008 21:00:44 -0500

Colin wrote:

> I have two matrices that are 1 x 130943 and contain hex values.

> I want to be able to verify that they are in fact identical matrices but only one is shifted
> with respect to the other.

Do you only need to know that they -are- identical (but perhaps shifted), or do you need to
know the amount of the shift?

And do you happen to have any constraint on how much shift there would be? For example,
would it just happen to be the case that the shift would be by an even number of positions?

Is there exactly 1 hex digit per array location?

Would a fast "Not the same" or "Might be the same" be useful to you? e.g., are the
arrays often different and being the same is the much less common case that you can
afford to take longer to prove? For example, when two arrays are different, then
their histograms would often be different, so if the histograms are different then
you know [relatively quickly] that the arrays are not shifts of each other, and if
the histograms are the same then you could run a more detailed test.

--
.signature note: I am now avoiding replying to unclear or ambiguous postings.
Please review questions before posting them. Be specific. Use examples of what you mean,
of what you don't mean. Specify boundary conditions, and data classes and value
relationships -- what if we scrambled your data or used -Inf, NaN, or complex(rand,rand)?

Re: Check if two shifted matrices are equal

Colin — Thu, 06 Nov 2008 21:07:02 -0500

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

Hi! Thanks for the quick reply.

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?

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.

Re: Check if two shifted matrices are equal

Colin — Thu, 06 Nov 2008 21:12:01 -0500

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

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.

There is a hex value at exactly every index.

Re: Check if two shifted matrices are equal

Roger Stafford — Thu, 06 Nov 2008 23:16:04 -0500

"Colin " <colinzhe@gmail.com> wrote in message <gevia6$2hk$1@fred.mathworks.com>...
> Hi all,
>
> I have two matrices that are 1 x 130943 and contain hex values.
>
> I want to be able to verify that they are in fact identical matrices but only one is shifted with respect to the other.
>
> A simple example could be:
>
> M1 =
> a
> b
> c
> d
>
> M2 =
> b
> c
> d
> a
>
> 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.
>
> Perhaps there is a faster/easier way to accomplish this?
>
> Thanks for any tips and insight,
> czhe

You might consider two nested while-loops 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.

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 while-loop until the first mismatch occurs.

Roger Stafford

Re: Check if two shifted matrices are equal

Bruno Luong — Fri, 07 Nov 2008 00:59:02 -0500

"Colin " <colinzhe@gmail.com> wrote in message <gevia6$2hk$1@fred.mathworks.com>...

>
> Perhaps there is a faster/easier way to accomplish this?
>

a=[7 0 3 0 1 8 7 3 10 0];
b=[3 0 1 8 7 3 10 0 7 0];

% Engine
shift=findstr(b,[a a])-1

% Check
n = length(a);

if isempty(shift)
  fprintf('cannot match after circular shift')
else
  shift = shift(1);
  shiftedidx = mod((1:n)+shift-1,length(a))+1;
  isequal(b, a(shiftedidx ))
end

% Bruno

Re: Check if two shifted matrices are equal

Jos — Fri, 07 Nov 2008 09:51:02 -0500

"Colin " <colinzhe@gmail.com> wrote in message <gevia6$2hk$1@fred.mathworks.com>...
> Hi all,
>
> I have two matrices that are 1 x 130943 and contain hex values.
>
> I want to be able to verify that they are in fact identical matrices but only one is shifted with respect to the other.
>
> A simple example could be:
>
> M1 =
> a
> b
> c
> d
>
> M2 =
> b
> c
> d
> a
>
> 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.
>
> Perhaps there is a faster/easier way to accomplish this?
>
> Thanks for any tips and insight,
> czhe

This is pretty quick:

%== Start of Code ==
% some data
a = rand(100000,1) ;
% create a shifted vector
nc = ceil(numel(a)*rand)
b = circshift(a,nc) ; % shifted

% try different types
% b = rand(size(a)) ; % completely different
% b([1 2]) = b([2 1]) ; % swap two elements
% b = a ; % no shift

[i,i] = ismember(a,b) ;
di = abs(diff(i)) ;
ShiftN = - find(di>1) ; % minus sign!

AreTheSame = numel(ShiftN)<2
if AreTheSame,
    ShiftN = max([ShiftN ; numel(a) + ShiftN ; 0])
    b2 = circshift(a,ShiftN) ;
    isequal(b2,b)
end
%== End of Code ==

hth
Jos

Re: Check if two shifted matrices are equal

Colin — Fri, 07 Nov 2008 15:24:02 -0500

Thank you all very much! This helps a lot.