linq排序的另一個列表的子集

Question

關於查找是否有一個列表是另一個列表的子集，有很多很多的問題。

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

我似乎無法找到一個佔爲了

在給定的順序：

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

子序列...

2,5,8,1,9 true

1,2,5,8,1真正

5,2,1假

1,2,5,1,8假

1,1,2真正

1,1,1,2假

Answer 1

中的順序是顯著名單是串的概念的推廣。因此你想使用子串查找算法。

有幾種可能性，但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 2

不幸的是，在.NET中沒有這樣的功能。你需要Knuth-Morris-Pratt算法。一個人已經實施它作爲LINQ擴展https://code.google.com/p/linq-extensions/

Answer 3

有一個解決方法的限制。您可以將枚舉更改爲字符串，然後使用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 4

你可以建立自己的分機，我寫了一個簡單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 5

Th是對我的作品：

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 6

可能使用加入可以讓你什麼你想。加入將返回匹配的記錄。如果記錄計數大於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; } 
}