linq 另一个列表的有序子集

Question

SO 上有很多关于查找一个列表是否是另一个列表的子集的问题。

即bool isSubset = !t2.Except(t1).Any();

我好像找不到一个占订单的

如给定的序列：

1,1,2,5,8,1,9,1,2

子序列...

2,5,8,1,9 真

1,2,5,8,1 真

5,2,1 假

1,2,5,1,8 假

1,1,2 真

1,1,1,2 假

Answer 1

遗憾的是.net中没有这样的功能。为此，您需要 Knuth–Morris–Pratt 算法。一个人已经将它实现为 linq 扩展 https://code.google.com/p/linq-extensions/

Answer 2

该限制有一个解决方法。您可以将枚举更改为字符串，然后使用 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

Answer 3

你可以构建自己的扩展，我写了一个简单的 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;
    }
}

Answer 4

这对我有用：

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

Answer 5

顺序重要的列表是字符串概念的概括。因此，您想使用子串查找算法。

有多种可能性，但 Knuth–Morris–Pratt 是一个不错的选择。它有一些初始的 Θ(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

Answer 6

可能使用 join 可以得到你想要的。加入将 return 匹配的记录。如果记录数大于 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; }
}

linq 另一个列表的有序子集

linq ordered subset of another list

c#

linq

set