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

список, в котором порядок является существенным является обобщением понятия строки. Поэтому вы хотите использовать алгоритм подстроки.

Существует несколько возможностей, но Кнут-Моррис-Пратт - хороший выбор. Он имеет некоторые начальные накладные расходы Θ (m), где m - длина искомого искателя, а затем находит в Θ (n), где n - это расстояние до искомого искателя или длина всего списка, если его нет , Это бьет простой пункт за пунктом сравнения, который является Θ ((п-т + 1) м):

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. Для этого вам нужен Кнут-Моррис-Пратт-алго. Один парень уже реализовал его как расширение 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:

Console App для тестирования:

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

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

Может использовать присоединиться вы можете получить то, что вы хотеть. 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; } 
}