是否有一种算法(名称、实现)给出了两个相同排序/内容但起始项不同的列表来测试是否相等

Question

当然有一些东西，但谷歌搜索并不能提供我想要的东西。也许是因为我不知道要查找的算法的名称？

基本上，我有两个内容和大小相同的列表。

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

请注意，两个列表的顺序相同。ie:List2可以被看作是从List1中的上一个位置到最后一个位置的开始，并从List1的开始继续迭代，直到回到起始位置。

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

然后，这两个列表被认为是等效的。

以下两个列表不是：

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

更新

我现在正在做的是将List1连接到它自己，并在其中搜索List2

我觉得这没用。

假设我想迭代每个列表一次？

更新

好的，最后我使用了上面描述的算法：检查一个字符串是否是另一个字符串的旋转而不连接并根据我的数据类型进行调整。

Answer 1

在List1+List1中搜索List2。您可以使用KMP在线性时间内做到这一点。

UPDATE：优化代码，使其在最佳情况下至少与其他解决方案一样快，在最坏情况下速度惊人

一些代码。该代码使用了KMP的修改版本，该版本接收List1，但实际上考虑到它已经加倍了（为了性能）。

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

因此，首先我们需要一种方法来多次移动列表，在这样做的同时包装项目

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

在这里，我们可以通过给定的移位对序列进行迭代。

有了这个，我们所需要做的就是看看其中一个列表是否与另一个列表相等，该列表被移动到其大小的任何次数。

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)));
}

请注意，虽然该算法在最坏的情况下确实具有n^2的复杂性，但由于SequenceEqual和Any的短路，它实际上对几乎任何实际数据都不会做那么多工作。

Answer 3

怎么样：

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

更新

当有很多不相等的列表时，（到目前为止）更有效的算法是Juan的算法。

我更新了答案。

---

下面是一个LinqPad代码，用于显示几种算法之间的性能比较。

它使用@GitHub:zaus/LinqPad.MyExtensions.cs 中的LinqPad扩展

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)));
}

结果是：

|      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   |  

获胜者：AreEqualByRotation

更新

胡安·洛佩斯指出，当弦不相等时，他的解决方案会更快。

以下是这个输入和1000次迭代的结果：

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  |  

获胜者：CheckIt