另一列表的linq有序子集

顺序重要的列表是对以下概念的概括: 一串 。因此,您希望使用子字符串查找算法。

有几种可能性,但KnuthMorrisPratt是一个不错的选择。它有一些初始(m)开销,其中m是所搜索的子列表的长度,然后在(n)中查找,其中n是所搜索子列表的距离,如果不存在,则是整个列表的长度。这胜过了简单的逐项比较,即((n-m+1)m):

public static class ListSearching
{
  public static bool Contains<T>(this IList<T> haystack, IList<T> needle)
  {
    return Contains(haystack, needle, null);
  }
  public static bool Contains<T>(this IList<T> haystack, IList<T> needle, IEqualityComparer<T> cmp)
  {
    return haystack.IndexOf(needle, cmp) != -1;
  }
  public static int IndexOf<T>(this IList<T> haystack, IList<T> needle)
  {
    return IndexOf(haystack, needle, null);
  }
  public static int IndexOf<T>(this IList<T> haystack, IList<T> needle, IEqualityComparer<T> cmp)
  {
    if(haystack == null || needle == null)
      throw new ArgumentNullException();
    int needleCount = needle.Count;
    if(needleCount == 0)
      return 0;//empty lists are everywhere!
    if(cmp == null)
      cmp = EqualityComparer<T>.Default;
    int count = haystack.Count;
    if(needleCount == 1)//can't beat just spinning through for it
    {
      T item = needle[0];
      for(int idx = 0; idx != count; ++idx)
        if(cmp.Equals(haystack[idx], item))
          return idx;
      return -1;
    }
    int m = 0;
    int i = 0;
    int[] table = KMPTable(needle, cmp);
    while(m + i < count)
    {
      if(cmp.Equals(needle[i], haystack[m + i]))
      {
        if(i == needleCount - 1)
          return m == needleCount ? -1 : m;//match -1 = failure to find conventional in .NET
        ++i;
      }
      else
      {
        m = m + i - table[i];
        i = table[i] > -1 ? table[i] : 0;
      }
    }
    return -1;
  }
  private static int[] KMPTable<T>(IList<T> sought, IEqualityComparer<T> cmp)
  {
    int[] table = new int[sought.Count];
    int pos = 2;
    int cnd = 0;
    table[0] = -1;
    table[1] = 0;
    while(pos < table.Length)
      if(cmp.Equals(sought[pos - 1], sought[cnd]))
        table[pos++] = ++cnd;
      else if(cnd > 0)
        cnd = table[cnd];
      else
        table[pos++] = 0;
    return table;
  }
}

测试:

var list = new[]{ 1, 1, 2, 5, 8, 1, 9, 1, 2 };
Console.WriteLine(list.Contains(new[]{2,5,8,1,9})); // True
Console.WriteLine(list.Contains(new[]{1,2,5,8,1})); // True
Console.WriteLine(list.Contains(new[]{5,2,1}));     // False
Console.WriteLine(list.Contains(new[]{1,2,5,1,8})); // False
Console.WriteLine(list.Contains(new[]{1,1,2}));     // True
Console.WriteLine(list.Contains(new[]{1,1,1,2}));   // False

不幸的是,.net中没有这样的功能。你需要KnuthMorrisPratt算法。一个人已经将其实现为linq扩展 https://code.google.com/p/linq-extensions/

这对我有用:

var source = new [] { 1,1,2,5,8,1,9,1,2 };

Func<int[], int[], bool> contains =
    (xs, ys) =>
        Enumerable
            .Range(0, xs.Length)
            .Where(n => xs.Skip(n).Take(ys.Length).SequenceEqual(ys))
            .Any();

Console.WriteLine(contains(source, new [] { 2,5,8,1,9 })); // true
Console.WriteLine(contains(source, new [] { 1,2,5,8,1 })); // true
Console.WriteLine(contains(source, new [] { 5,2,1 })); // false
Console.WriteLine(contains(source, new [] { 1,2,5,1,8 })); // false
Console.WriteLine(contains(source, new [] { 1,1,2 })); // true
Console.WriteLine(contains(source, new [] { 1,1,1,2 })); // false

有一种解决该限制的方法。可以将enumerable更改为字符串,然后使用 Contains 方法

 var t1 = new List<int> {1, 1, 2, 5, 8, 1, 9, 1, 2};
         var t2 = new List<int> {2,5,8,1,9};
         var t3 = new List<int> {5,2,1};

         var t1Str = String.Join(",", t1);

t1Str.Contains(String.Join(",", t2););//true
t1Str.Contains(String.Join(",", t3););//false

您可以构建自己的扩展,我编写了一个简单的IsSubset方法:

用于测试的控制台应用程序:

class Program
{
    static void Main(string[] args)
    {
        var list = new List<int> { 1, 3, 5, 2, 4, 6 };
        var subList = new List<int> { 3, 5};
        var subList2 = new List<int> { 1, 4 };

        bool isSublist1 = subList.IsSubset(list);

        bool isSublist2 = subList2.IsSubset(list);

        Console.WriteLine(isSublist1 + "; " + isSublist2);
        /* True; False */

        Console.ReadKey();
    }

}

IEnumerable扩展:

public static class IEnumerableExtensions
{
    public static bool IsSubset<T>(this IEnumerable<T> subsetEnumerable, IEnumerable<T> enumerable)
    {
        var found = false;

        var list = enumerable as IList<T> ?? enumerable.ToList();
        var listCount = list.Count();

        var subsetList = subsetEnumerable as IList<T> ?? subsetEnumerable.ToList();
        var posListCount = subsetList.Count();

        /* If the SubList is bigger, it can't be a sublist */
        if (listCount < posListCount) { 
            return false;
        }

        /* find all indexes of the first item of the sublist in the list */
        var firstElement = subsetList.First();
        var indexes = new List<int>();
        var index = 0;
        foreach (var elem in list)
        {
            if (elem.Equals(firstElement))
            {
                indexes.Add(index);
            }
            index++;
        }

        /* check all first item founds for the subsequence */
        foreach (var i in indexes)
        {
            int x=0;
            for (x = 0; x < posListCount && (i + x) < listCount; x++)
            {
                if (!Equals(subsetList[x], list[(i + x)]))
                {
                    found = false;
                    break;
                }
                found = true;
            }

            if (x + 1 < posListCount)
                found = false;
        }

        return found;
    }
}

可能正在使用join可以得到你想要的。联接将返回匹配的记录。如果记录计数大于0,则存在匹配项,否则不存在匹配项。

下面我通过示例代码进行了解释:

class Program
{
    static void Main(string[] args)
    {
        List<Employee> empList = new List<Employee> 
        {
            new Employee{EmpID = 1},
            new Employee{EmpID = 1},
            new Employee{EmpID = 2},
            new Employee{EmpID = 5},
            new Employee{EmpID = 8},
            new Employee{EmpID = 1},
            new Employee{EmpID = 9},
            new Employee{EmpID = 1},
            new Employee{EmpID = 2}
        };

        List<Manager> mgrList = new List<Manager> 
        {
            new Manager{ManagerID = 7},
            new Manager{ManagerID = 3},
            new Manager{ManagerID = 6}               
        };

        var result = (from emp in empList
                     join mgr in mgrList on emp.EmpID equals mgr.ManagerID
                     select new { emp.EmpID}).Count();

        Console.WriteLine(result);
        Console.ReadKey();
    }
}

public class Employee
{ 
    public int EmpID { get; set; } 
}

public class Manager
{ 
    public int ManagerID { get; set; }
}