Как получить наибольшее совпадение в количестве наборов, важно очень важно

Question

Мне нужно найти способ вернуть самое длинное соответствие, найденное в количестве наборов/списков (значения возвращаются только один раз), когда порядок элементов важен. список не циклический.

Соответствие - это последовательность значений, которая существует во всех списках и поддерживает один и тот же порядок элементов во всех списках.

например. 1:

List<int> list1 = new List<int> { 1, 2, 3, 4, 7, 9 }; 
    List<int> list2 = new List<int> { 1, 2, 5, 6, 3, 4, 7, 9 }; 
    List<int> list3 = new List<int> { 1, 2, 3, 6, 8, 9 }; 
    List<int> list4 = new List<int> { 1, 2, 5, 6, 8, 9 }; 

результат {1, 2}

например, 2:

 List<int> list1 = new List<int> { 2, 3, 6, 8, 1, 18 }; 
    List<int> list2 = new List<int> { 2, 3, 4, 6, 8, 1, 18, 19, 17, 14 }; 
    List<int> list3 = new List<int> { 2, 5, 6, 8, 1, 18, 16, 13, 14 }; 
    List<int> list4 = new List<int> { 2, 6, 8, 1, 18, 19, 17, 14 }; 

результат {6, 8, 1, 18}

матч не должен быть найден в начале или в конце, и может быть на любой части любого списка.

Я надеюсь, что я объяснил свою проблему достаточно хорошо :)

Спасибо!

Answer 1

Вы можете построить карту из пар целых чисел отсчета сколько из списков они появляются смежны в

Псевдо-код:.

For each list L { 
    For each adjacent pair (x, y) in L { 
     Counts[x, y] += 1 
    } 
} 

Теперь вы можете перебирать первый список (или самый короткий список) и найдите самый длинный пробег, чтобы каждая смежная пара (x, y) в пробеге с Counts [x, y] показывала, что пара появляется в каждом списке.

Псевдо-код:

run = [] 
best_run = [] 
For x in L[0] { 
    if len(run) is zero or Counts[run[len(run)-1], x] == number of lists { 
     run = run + x 
    } else { 
     run = [x] 
    } 
    if run is longer than best_run { 
     best_run = run 
    } 
} 

Это работает с учетом предположения в этом вопросе, что не целое число не появляется дважды в одном списке.

Этот алгоритм работает в O (N) времени, где N - сумма длин всех списков.

Answer 2

Вот мой подход.

Сначала я нужен способ, чтобы сравнить списки:

public class ListCompare<T> : IEqualityComparer<List<T>> 
{ 
    public bool Equals(List<T> left, List<T> right) 
    { 
     return left.SequenceEqual(right); 
    } 

    public int GetHashCode(List<T> list) 
    { 
     return list.Aggregate(0, (a, t) => a^t.GetHashCode()); 
    } 
} 

Далее способ произвести все подпоследовательности список источников:

Func<List<int>, IEnumerable<List<int>>> subsequences = xs => 
    from s in Enumerable.Range(0, xs.Count) 
    from t in Enumerable.Range(1, xs.Count - s) 
    select xs.Skip(s).Take(t).ToList(); 

Теперь я могу создать список списков:

var lists = new [] { list1, list2, list3, list4, }; 

Наконец-то запрос, который тянет все это вместе:

var answer = 
    lists 
     .Skip(1) 
     .Aggregate(
      subsequences(lists.First()), 
      (a, l) => a.Intersect(subsequences(l), new ListCompare<int>())) 
     .OrderByDescending(x => x.Count) 
     .FirstOrDefault(); 

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

Answer 3

1. Сначала приготовьте упорядоченную комбинацию int из кратчайшего списка
2. Сравнить другие, чем короткий список с комбинацией списков. Для простого сравнения списков я просто конвертирую в string и использую string.Contains()
3. Возвращайтесь немедленно, если найдете совпадение, так как позиции слева - следующий или более короткий.

---

public static List<int> GetLongestMatch(params List<int>[] all) 
{ 
    var shortest = all.Where(i => i.Count == all.Select(j => j.Count).Min()).First(); 
    var permutations = (from length in Enumerable.Range(1, shortest.Count) 
         orderby length descending 
         from count in Enumerable.Range(1, shortest.Count - length + 1) 
         select shortest.Skip(count - 1).Take(length).ToList()) 
         .ToList(); 

    Func<List<int>, string> stringfy = (list) => { return string.Join(",", list.Select(i => i.ToString()).ToArray()); }; 
    foreach (var item in permutations) 
    { 
     Debug.WriteLine(string.Join(", ", item.Select(i => i.ToString()).ToArray())); 
     if (all.All(list => stringfy(list).Contains(stringfy(item)))) 
     { 
      Debug.WriteLine("Matched, skip process and return"); 
      return item; 
     } 
    } 
    return new List<int>(); 
} 

Использование

var result = GetLongestMatch(list1, list2, list3, list4); 

Результат

2, 3, 6, 8, 1, 18 
2, 3, 6, 8, 1 
3, 6, 8, 1, 18 
2, 3, 6, 8 
3, 6, 8, 1 
6, 8, 1, 18 
Matched, skip process and return