Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Check if two shifted matrices are equal

Subject: Check if two shifted matrices are equal

From: Colin

Date: 6 Nov, 2008 19:59:02

Message: 1 of 8

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

Subject: Check if two shifted matrices are equal

From: Walter Roberson

Date: 6 Nov, 2008 21:00:44

Message: 2 of 8

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)?

Subject: Check if two shifted matrices are equal

From: Colin

Date: 6 Nov, 2008 21:07:02

Message: 3 of 8

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.

Subject: Check if two shifted matrices are equal

From: Colin

Date: 6 Nov, 2008 21:12:01

Message: 4 of 8

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.

Subject: Check if two shifted matrices are equal

From: Roger Stafford

Date: 6 Nov, 2008 23:16:04

Message: 5 of 8

"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

Subject: Check if two shifted matrices are equal

From: Bruno Luong

Date: 7 Nov, 2008 00:59:02

Message: 6 of 8

"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

Subject: Check if two shifted matrices are equal

From: Jos

Date: 7 Nov, 2008 09:51:02

Message: 7 of 8

"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

Subject: Check if two shifted matrices are equal

From: Colin

Date: 7 Nov, 2008 15:24:02

Message: 8 of 8

Thank you all very much! This helps a lot.

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us