Suppose to have an array like this:

[1,2,3,4,5,6]

and another one like this (rotated):

[3,4,5,6,1,2]

Is there any easy way to tell that they are equal or shall I write a function to compare them?

EDIT: of course, the first array should NOT be equal with:

[4,3,5,6,1,2]

or

[1,2,3,4,5,6,7]

CodePudding user response：

If we have an array {a, b, c, .., z} and we want to find if it equals to {A, B, ..., Z} we can turn the problem into equivalent

Having abc...z string check if ABC...ZABC...Z string contains abc...z

To solve it we can use efficient Knuth-Morris-Pratt algorithm (t ~ O(n)) or if arrays are not very long use easy to implement naive prefix comparisons (t ~ O(n ** 2) in the worst case):

    private static bool MyEquals(int[] left, int[] right)
    {
        if (ReferenceEquals(left, right))
            return true;

        if (left is null || right is null)
            return false;

        if (left.Length != right.Length)
            return false;

        for (int start = 0; start < right.Length;   start)
        {
            bool found = true;

            for (int i = 0; i < left.Length;   i)
                if (right[(start   i) % right.Length] != left[i])
                {
                    found = false;

                    break;
                }

            if (found)
                return true;
        }

        return false;
    }

Note that

    left.OrderBy(x => x).SequenceEqual(right.OrderBy(x => x))

doesn't work; the counter example is {1, 2, 3, 4} vs. {1, 3, 2, 4} which should be not equal when the code above returns true.

CodePudding user response：

First, we check the first item of the second list in the first list. If it is found, we rotate it by the size of the index and compare two list:

    public bool listCompare(List<int>  l1, List<int>  l2)
    {
        int index = l1.FindIndex(a => a ==  l2[0]);
        if(index==-1) 
            return false;
        for(int i=0;i< index;i  )
        {
            int item = l1[0];
            l1.RemoveAt(0);
            l1.Add(item);
        }
        if(l1.SequenceEqual(l2))
              return true;
        else
            return false;
    }

The above solution is correct if the lists do not have duplicate items. If there is a duplicate item, all states must be checked. As follows:

    public bool listCompare2(List<int> l1, List<int> l2)
    {
        var tempList = l1.Select(item => item).ToList(); 

        var indexs = l1.Select((x, i) => new { x, i })
              .Where(x => x.x == l2[0])
              .Select(x => x.i).ToArray();
        for (int n = 0; n < indexs.Length; n  )
        {
            int rotateSize = indexs[n];
            for (int i = 0; i < rotateSize ; i  )
            {
                int item = l1[0];
                l1.RemoveAt(0);
                l1.Add(item);
            }
            if (l1.SequenceEqual(l2))
                return true;
            l1 = tempList;
        }

        return false;
    }