Creating a Boolean function that determines if two arrays are shift equivalent

Question

Two arrays:

a[] = {1 2 3 4}
b[] = {3 4 1 2}

The bottom array is simply the top array shifted to the right two places. If the top array can be right shifted to create the bottom array, we call them shift equivalent.

Here is my attempt at creating a function (I need to use a Boolean function) to determine if two arrays are "shift equivalent":

#include <iostream>
using namespace std;

bool equivalent(int a[], int b[], int size) {

    int value; // if 1 returns as truth
    int k; // counter to compare both arrays

    for (int j = 0; j <= size; j++) {
        for (int i = 0; i <= size; i++) {
            a[i] = a[i + j];
        }
    }

    for (k = 0; k <= size; k++) {
        if (a[k] != b[k]) {
            value = 0;
        } else value = 1;
    }

    return (value == 1);
}

int main() {
    int n;
    cout << "Please input a size " << endl;
    cin >> n;

    int *mtrx = new int[n];
    int *mtrx1 = new int[n];
    int x;
    for (x = 0; x < n; x++) {
        cout << "Please make entries for the first array: " << endl;
        cin >> mtrx[x];
    }
    x = 0;
    for (x = 0; x < n; x++) {
        cout << "Please make entries for the 2nd array: " << endl;
        cin >> mtrx1[x];
    }

    bool answr = equivalent(mtrx, mtrx1, n = n - 1);

    if (answr) {
        cout << "They are shift equivalent." << endl;
    } else {
        cout << "They are not shift equivalent." << endl;
    }

    delete[] mtrx;
    delete[] mtrx1;

    system("PAUSE");
    return 0;
}

When I execute my program, I use array1 = {1 2 3} and array2 = {3 1 2} to test shift equivalency. They are supposed to be, but my program says they aren't.

Answer 1

One problem which I see in your code is that you access memory beyond the array. If you add two indices, you have to make sure that they "wrap around" if you want to treat your array cyclic. This can be done with a modulo. Instead of

a[i + j]

you should write

a[(i + j) % size]

I'd split your algorithm into two parts: First, write a function which tests if a equals b with a shift of shift. Then, within a second function (the final equivalent function), test for all possible values for shift.

bool equivalentFixed(int a[], int b[], int size, int shift) {
    for (int i = 0; i < size; ++i) {
        if (a[i] != a[(i + shift) % size])
            return false;
    }
    return true;
}

bool equivalent(int a[], int b[], int size) {
    for (int shift = 0; shift < size; ++shift) {
        if (equivalentFixed(a, b, size, shift))
            return true;
    }
    return false;
}

If you look close, you don't see any local variable to hold (store) the value if the arrays are equivalent. Indeed, your code has a problem here, too, since you always overwrite the old status with the new one for each single entry you compare. So if the comparison fails anywhere during scanning the arrays, but the very last entry compares to equal, you return "yes, they are equal", since you have overwritten the status.

Now have a look at my equivalent implementation. I scan for different offsets (shift) if the arrays compare equal. Let's focus on this function, not how the comparison is done in the other function. The point is: We have to return true if for any shift they compare equal, not for the last one and not for all.

The idea to solve this is to break the loop (stop) if you found a solution. You can even return the whole function, since you know the complete return value, namely true.

If for no possible shift the comparison is true, we didn't find any possible shift, so they aren't "shift equivalent".

I used a very similar approach to implement the comparison of two arrays with a fixed shift (equivalentFixed). Can you explain how this is done?