Are the two circular buffers equal? (Ignoring the shift)
I have two circular buffers - how can I tell if this is just a shift of the other?
For example, with B1 = 1,1,2,1,8,1,5,7
, B2 = 2,1,8,1,5,7,1,1
you could say that B1 and B2 are equal because I can rotate one of them to get the other.
What is the best algorithm to test this equality? The obvious test is in O(n^2)
(just compare buffer steps - n
) starting at each of the elements n
), but I believe I've seen a linear time algorithm. Could you point me to this?
source to share
Assuming B1
both B2
are the same length, your question is equivalent to asking "is B2
substring B1 + B1
" ( B1
related to itself).
For example: A 4-element string is a rotation 1234
if and only if it is a substring 12341234
.
Checking that one string is a substring of another can be done in a linear fashion using the KMP algorithm .
source to share
if your buffer has integers, I thought maybe you could use the fact that adding as a commutative property (a+b == b+a)
means that the beginning of the list doesn't matter. but on the other hand, the order of the elements (1+2+3+4) = (3+1+2+4)
, to make sure the elements are in the correct order, we can link them in pairs or trios. to better enforce chain order .. (12+23+34+41)
or something like that ..
var B1 = [1,1,2,1,8,1,5,7]
var B2 = [2,1,8,1,5,7,1,1]
var B3 = [2,1,8,1,5,7,1,4]
function checksum(buff)
{
var sum = 0
for(var i = 0 ; i < buff.length;i++)
{
var a = buff[i];
var b = buff[(i+1)%buff.length];
var c = buff[(i+2)%buff.length];
var n = ((a*100) + (b * 10) + c);
sum += n;
}
return sum;
}
console.log(checksum(B1) == checksum(B2))//true
console.log(checksum(B1) == checksum(B3))//false
this is an "order sensitive" circular checksum
but like any hash function, collisions and false positives will occur, so you need a secondary comparison method.
don't know if i am on the right track .. hope someone can help make this better or refute completely.
source to share