compare arrays integer values with shifted values

Question

I want create function which compares two arrays so that if they have the same values in a certain order (which may be maybe shifted) returns true.

For example

int arr1[] = {1,2,3,4,5}
int arr2[] = {3,4,5,1,2}

are the same, or true

while

int arr1[] = {1,2,3,4,5}
int arr2[] = {3,4,5,2,1}

are not same, and so false.

Any ideas?

Answer 1

You may be interested in the C++ equivalent for this. It's instructive to see how the Standard Library provides much higher-level abstractions than are available to the C programmer.

First of all, we'll want a sensible signature for our function. Let's make it a template, so we can use std::array as happily as std::vector and struct Foo as happily as int:

template<typename T>
bool equals_rotated(const std::vector<T>& a, const std::vector<T>& b);

And some simple tests:

int main()
{
    const auto e = equals_rotated<int>;
    return !e({}, {})
        +   e({1, 2, 3, 4} , {1, 2, 3})
        +  !e({1, 2, 3}    , {1, 2, 3})
        +   e({1, 2, 3, 4} , {1, 2, 4, 3})
        +  !e({1, 2, 3, 4} , {4, 1, 2, 3})
        ;
}

The implementation is straightforward. We know that if the arrays differ in length then they can't be equivalent; conversely, if they are identical, they must be equivalent. So let's return early in those cases:

if (a.size() != b.size())
    return false;
if (a == b)
    return true;

For the general case, we can make a concatenation of a and itself, and then test whether that contains b as a subsequence. This will have an impact on the memory requirement, but it makes for a simple implementation:

auto v = a;
v.reserve(2*a.size());
std::copy(a.begin(), a.end(), std::back_inserter(v));
return std::search(v.begin(), v.end(), b.begin(), b.end()) != v.end();

---

If we put that all together, include the necessary headers, and add a wrapper so that we can call it from C, we get:

#include <algorithm>
#include <iterator>
#include <vector>

template<typename IterA, typename IterB>
bool equals_rotated(IterA a_begin, IterA a_end, IterB b_begin, IterB b_end)
{
    // trivial tests
    if (a_end - a_begin != b_end - b_begin)
        return false;
    if (std::equal(a_begin, a_end, b_begin, b_end))
        return true;
    // Otherwise, make a copy of a+a
    std::vector<typename std::iterator_traits<IterA>::value_type> v;
    v.reserve(2 * (a_end - a_begin));
    const auto ins = std::back_inserter(v);
    std::copy(a_begin, a_end, ins);
    std::copy(a_begin, a_end, ins);
    // and test whether it contains b
    return std::search(v.begin(), v.end(), b_begin, b_end) != v.end();
}

template<typename T>
bool equals_rotated(const std::vector<T>& a, const std::vector<T>& b)
{
    return equals_rotated(a.begin(), a.end(), b.begin(), b.end());
}

extern "C" {
    bool is_rotated_array(int *a, size_t a_len, int *b, size_t b_len)
    {
        return equals_rotated(a, a+a_len, b, b+b_len);
    }
}

int main()
{
    const auto e = equals_rotated<int>;
    return !e({}, {})
        +   e({1, 2, 3, 4} , {1, 2, 3})
        +  !e({1, 2, 3}    , {1, 2, 3})
        +   e({1, 2, 3, 4} , {1, 2, 4, 3})
        +  !e({1, 2, 3, 4} , {4, 1, 2, 3})
        ;
}

Answer 2

Here you are

#include <stdio.h>

int is_equivalent(const int a[], const int b[], size_t n)
{
    int success = 0;

    for ( size_t m = 0; !success && m < n;  )
    {
        // Try to find in the array a the first element of the array b
        // If there is no such an element then the arrays are different.
        // Otherwise compare elements of the arrays starting from the
        // found element in a and the first element in b
        while (m < n && a[m] != b[0]) ++m;

        if (m != n)
        {
            size_t i = 1;
            size_t j = ++m % n;

            while (i < n && b[i] == a[j])
            {
                ++i; ++j;
                j %= n;
            }

            success = i == n;
        }
    }

    return success;
}

int main( void )
{
    {
        int a[] = { 1, 2, 3, 4, 5 };
        int b[] = { 3, 4, 5, 1, 2 };

        printf("The arrays are equivalent: %d\n",
            is_equivalent(a, b, sizeof(a) / sizeof(*a)));
    }

    {
        int a[] = { 1, 2, 3, 4, 5 };
        int b[] = { 3, 4, 5, 2, 1 };

        printf("The arrays are equivalent: %d\n",
            is_equivalent(a, b, sizeof(a) / sizeof(*a)));
    }

    return 0;
}

The program output is

The arrays are equivalent: 1
The arrays are equivalent: 0

Answer 3

#include <stdio.h>

int isArraySame(int arr1[], int arr2[], int len1, int len2){
    int var1=0;
    int var2=0;
    int index=0;

    for (index=0;index<len1;index++){
        var1+=arr1[index];
    }

    for (index=0;index<len2;index++){
        var2+=arr2[index];
    }

    if (var1==var2) return 1;
    return 0;
}

int main(){
    int arr1[] = {1,2,3,4,5};
    int arr2[] = {3,4,5,1,2};
    if (isArraySame(arr1, arr2, 5, 5)) {
        printf("true");
    } else {
        printf("false");
    }
    return 0;
}

Answer 4

try this

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool check(size_t size, int arr1[], int arr2[]){
    int *temp = malloc(size * 2 * sizeof *temp);
    memcpy(temp, arr1, size * sizeof *temp);
    memcpy(temp+size, arr1, size * sizeof *temp);//[1,2,3] --> [1,2,3,1,2,3]

    size_t i;
    for(i = 0; i < size; ++i)
        if(memcmp(temp+i, arr2, size * sizeof *temp) == 0)
            break;
    free(temp);
    return i != size;
}    

#define TEST(size, a1, a2) puts(check(size, a1, a2) ? "same" : "not same")

int main(void) {
    int arr1[] = {1,2,3,4,5};
    int arr2[] = {3,4,5,1,2};
    int arr3[] = {3,4,5,2,1};
    int arr4[] = {1, 0, 1, 1, 0};
    int arr5[] = {1, 0, 1, 0, 1};
    size_t size = sizeof(arr1)/sizeof(*arr1);

    TEST(size, arr1, arr2);
    TEST(size, arr1, arr3);
    TEST(size, arr4, arr5);
}

Answer 5

Well, if the arrays are just rotated versions of each other, they must be of equal length and there must exist at least one offset, such that rotate(arr1, offset) == arr2.

Thus we know that concat(arr2, arr2) must be equivalent to rotate(concat(arr1, arr1), offset) and thus must contain arr1 without rotation at position offset.

And there we are with the classical substring-matching problem. There won't be any better solution to this problem than the algorithms to solve the former simply because they are equivalent.

A pretty simple solution to this problem would be elimination of probable offsets:

//generate a list of offsets from the first element in arr1
list offsets = indicesOf(arr1[0], arr2)

int i = 0
while !offsets.empty && i < length(arr1):
    //generate the rotational offsets of the next char
    list nextoffsets = indicesOf(arr1[i], arr2)
    //make offsets the list of offsets that are valid for all elements up to arr1[i]
    offsets = intersection(offsets, nextoffsets)

    i++

return !offsets.empty