Is there an algorithm (name, implementation) that given two lists of the same ordering/content but different starting item to test for equality?

Question

Surely there is something out there but googling doesn't give me what I'm looking for. Perhaps it's because I don't know the name of the algorithm to lookout for?

Basically, I have two lists with the same content and size.

List1: {10, 30, 2, 4, 4}
List2: {4, 4, 10, 30, 2}

Notice that the sequence is the same for both lists. ie: List2 can be seen as a starting from the previous to last position in List1 and continuing to iterate from the start of List1 until back at the starting position.

List1: {10, 30, 2, 4, 4} 10, 30, 2
                   |  |  |   |   |
List2:            {4, 4, 10, 30, 2}

The two lists are then considered equivalent.

The following two lists are not:

List1: {10, 30, 2, 4, 3} 10, 30, 2
                   |  |  X   X   |
List2:            {4, 4, 30, 10, 2}

Update

What I am doing right now is having List1 concatenated to itself and searching List2 inside of it.

I feel this is innefficient.

Suppose I want to iterate each list once?

Update

Ok, in the end I went with the algo described at: Check if a string is rotation of another WITHOUT concatenating and adapted it to my data types.

Answer 1

Search for List2 inside List1+List1. You can use KMP to do that in linear time.

UPDATE: optimized the code to be at least as fast as other solutions in the best case and amazingly faster in the worst-case

Some code. The code uses a modified version of KMP, that receives List1, but actually considers as it was already doubled (for performance).

using System;
using System.Collections.Generic;
using System.Linq;

namespace Test
{
    public class CyclicKMP<T> {
        private readonly IList<T> P;
        private readonly int[] F;
        private readonly EqualityComparer<T> comparer;

        public CyclicKMP(IList<T> P) {
            this.comparer = EqualityComparer<T>.Default;
            this.P = P;
            this.F = new int[P.Count+1];

            F[0] = 0;  F[1] = 0;  
            int i = 1, j = 0;
            while(i<P.Count) {
                if (comparer.Equals(P[i], P[j]))
                    F[++i] = ++j;
                else if (j == 0)
                    F[++i] = 0;
                else
                    j = F[j];
            }
        }

        public int FindAt(IList<T> T, int start=0) {
            int i = start, j = 0;
            int n = T.Count, m = P.Count;

            while(i-j <= 2*n-m) {
                while(j < m) {
                    if (comparer.Equals(P[j], T[i%n])) {
                        i++; j++;
                    } else break;
                }
                if (j == m) return i-m;
                else if (j == 0) i++;
                j = F[j];
            }
            return -1;
        }
    }

    class MainClass
    {
        public static bool Check<T>(IList<T> list1, IList<T> list2) {
            if (list1.Count != list2.Count)
                return false;
            return new CyclicKMP<T> (list2).FindAt (list1) != -1;
        }

        public static void Main (string[] args)
        {
            Console.WriteLine (Check(new[]{10, 30, 2, 4, 4}, new[]{4, 4, 10, 30, 2}));
            Console.WriteLine (Check(new[]{10, 30, 2, 4, 3}, new[]{4, 4, 10, 30, 2}));
        }
    }
}

Answer 2

So to start with we need a method to shift a list some number of times, wrapping the items while doing so. This is actually fairly straightforward to do:

public static IEnumerable<T> Shift<T>(this IEnumerable<T> source, int number)
{
    return source.Skip(number)
        .Concat(source.Take(number));
}

Here we're able to iterate over a sequence with a given shift.

With this all we need to do is see if one of the lists, shifted to any number of times up to its size, is equal to the other.

public static bool EqualWithShifting<T>(this IList<T> first, IList<T> second)
{
    return first.Count == second.Count &&
        Enumerable.Range(0, first.Count-1)
        .Any(shift => first.SequenceEqual(second.Shift(shift)));
}

Note that while this algorithm does have n^2 complexity in the worst case, due to the short circuiting of both SequenceEqual and Any this won't actually do nearly that much work for pretty much any real data.

Answer 3

How about:

void Main()
{

bool same = true;

var list1 = new List<int> {10, 30, 2, 4, 4};
var list2 = new List<int> {4, 4, 10, 30, 2};

var start = -1;

for(int i=0; i<list1.Count();i++)
{
 if(list1[0] == list2[i])
 { 
  start = i;
  break;
 }
}

start.Dump("Start");

if(-1 == start)
{ 
 same = false;
}
else
{
int x = 0;
int y = x + start;

int scanned = 0;

while(scanned < list2.Count)
{
 scanned++; 

 if(list1[x] == list2[y])
 {
    x++;
    y++;     if(y >= list2.Count)  {  y = 0; }
 }
 else
 {
   same = false;
   break;
 }
}
}

same.Dump("same");
}

// Define other methods and classes here

Answer 4

Update

The more efficient algo (so far) when having a lot of unequal lists is the one from Juan.

I updated the answer.

---

Here's a LinqPad code to show the perf comparison between several algorithm.

It uses LinqPad extensions from @GitHub : zaus / LinqPad.MyExtensions.cs

void Main()
{
    var first = "abcabcdefabcabcabcabcdefabcabc".ToList();
    var second = "abcdefabcabcabcabcdefabcabcabc".ToList();

    var p = new Perf<bool>
    {
        { "AreEqualByRotation", n => AreEqualByRotation (first, second) },
        { "IsEqualWithShifting", n => IsEqualWithShifting (first, second) },
        { "EqualWithShifting", n => EqualWithShifting (first, second) },
        { "CheckIt", n => CheckIt (first, second) },
    }.Vs("Shifting", 100000);
}

// Define other methods and classes here
bool AreEqualByRotation<T> (List<T> s1, List<T> s2)
{
    if (s1.Count != s2.Count)
        return false;

    for (int i=0; i<s1.Count; ++i)
    {
        bool res = true;
        int index = i;
        for (int j=0; j<s1.Count; ++j)
        {
            if (!s1[j].Equals(s2[index]))
            {
                res = false;
                break;
            }
            index = (index+1)%s1.Count;
        }
        
        if (res == true)
            return true;
    }
    return false;
}

bool IsEqualWithShifting<T> (List<T> list1, List<T> list2)
{
    if (list1.Count != list2.Count) 
        return false;

    for (var i = 0; i < list1.Count; i++)
    {
        for (var j = 0; j < list2.Count; j++)
        {
            int countFound = 0;

            while (list1[(i + countFound) % list1.Count].Equals(list2[(j + countFound) % list2.Count]) && countFound < list1.Count)
                countFound++;

            if (countFound == list1.Count)
                return true;
        }
    }

    return false;
}

public static IEnumerable<T> Shift<T>(IEnumerable<T> source, int number)
{
    return source.Skip(number)
        .Concat(source.Take(number));
}

public static bool EqualWithShifting<T>(IList<T> first, IList<T> second)
{
    return first.Count == second.Count &&
        Enumerable.Range(0, first.Count-1)
        .Any(shift => first.SequenceEqual(Shift(second, shift)));
}

public class KMP<T> {
   private readonly IList<T> P;
   private readonly int[] F;

   public KMP(IList<T> P) {
       this.P = P;
       this.F = new int[P.Count+1];

       F[0] = 0;  F[1] = 0;  
       int i = 1, j = 0;
       while(i<P.Count) {
           if (Object.Equals(P[i], P[j]))
               F[++i] = ++j;
           else if (j == 0)
               F[++i] = 0;
           else
               j = F[j];
       }
   }

   public int FindAt(IList<T> T, int start=0) {
       int i = start, j = 0;
       int n = T.Count, m = P.Count;

       while(i-j <= n-m) {
           while(j < m) {
               if (Object.Equals(P[j], T[i])) {
                   i++; j++;
               } else break;
           }
           if (j == m) return i-m;
           else if (j == 0) i++;
           j = F[j];
       }
       return -1;
   }
}

public static bool CheckIt<T> (IList<T> list1, IList<T> list2)
{
    return Check (list1, list2) != -1;
}

public static int Check<T>(IList<T> list1, IList<T> list2)
{
    if (list1.Count != list2.Count)
        return -1;
    return new KMP<T> (list2).FindAt (new List<T>(Enumerable.Concat(list1, list1)));
}

Result is :

|      Algorithm      |              Time spent             | Result |  
|:-------------------:|:-----------------------------------:|--------|  
| AreEqualByRotation  | 1262852 ticks elapsed (126.2852 ms) | True   |  
| IsEqualWithShifting | 1508527 ticks elapsed (150.8527 ms) | True   |  
| EqualWithShifting   | 4691774 ticks elapsed (469.1774 ms) | True   |  
| CheckIt             | 4079400 ticks elapsed (407.94 ms)   | True   |  

winner: AreEqualByRotation

Update

Juan Lopes remarked that his solution is faster when the strings are not equal.

Here's with this input and the results for 1000 iterations:

var first = new string('a', 200).ToList();
var second = (new string('a', 199)+'b').ToList();

|      Algorithm      |              Time spent                | Result |  
|:-------------------:|:--------------------------------------:|--------|  
| AreEqualByRotation  | 187613414 ticks elapsed (18761.3414 ms)| False  |  
| IsEqualWithShifting | Too long !!!                           | False  |  
| EqualWithShifting   | 766858561 ticks elapsed (76685.8561 ms)| False  |  
| CheckIt             | 28222332 ticks elapsed (2822.2332 ms)  | False  |  

winner: CheckIt