Самая длинная повторяющаяся последовательность с использованием только linq - PullRequest
Новая
       41

Самая длинная повторяющаяся последовательность с использованием только linq

0 голосов
/ 29 марта 2019

Как видно из заголовка, у меня есть задача найти самую длинную повторяющуюся последовательность в строке, и это должно быть сделано только с помощью linq - без ifs, без цикла, без попытки, присваивание допускается только при инициализации переменных, рекурсия позволил. Я нашел решение в Интернете, и я понимаю, что происходит, но я не могу преобразовать его в linq. Я не настолько знаком с ним. Буду очень признателен, если кто-нибудь сможет мне помочь. Вот ссылка на то, что я нашел - https://www.javatpoint.com/program-to-find-longest-repeating-sequence-in-a-string.

List<int> a = new List<int> {1, 2, 1, 2, 1, 2, 3, 2, 1, 2};
List<List<int>> aa = new List<List<int>>();
outerLoop(a);

var max = aa.Max(x => x.Count);
var m = from v in aa 
    where v.Count == max
    select v;
    m.Dump();

void outerLoop(List<int> list)
{
List<int> f = new List<int>();
f.AddRange(list.Skip(list.Count-1).Take(list.Count).ToList());
innerLoop(list, list.Skip(1).Take(list.Count).ToList());

f.ForEach(k => outerLoop(list.Skip(1).Take(list.Count).ToList()));
}


void innerLoop(List<int> l, List<int> subList)
{
List<int> f = new List<int>();
f.AddRange(subList.Skip(subList.Count-1).Take(subList.Count).ToList());
var tt = l.TakeWhile((ch, i) => i < subList.Count && subList[i] == ch).ToList();

aa.Add(tt);
f.ForEach(k => innerLoop(l, subList.Skip(1).Take(subList.Count).ToList()));
}

так что я придумал эту "красоту", я не думаю, что это хороший код, но я думаю, что он работает. Если кто-то заинтересован и хочет внести предложения, как сделать его лучше, он более чем рад:)

, если ввод int[] x= {1, 2, 1, 2, 1, 2, 3, 2, 1, 2} результат должен быть 1212

Ответы [ 2 ]

0 голосов
/ 29 марта 2019

Вот моя версия.Это не одно выражение LINQ, но использует только LINQ.Он возвращает все подпоследовательности одинаковой длины, если есть несколько ответов.Должно работать любой тип последовательности.Он был написан для использования только стандартных методов LINQ.

Он использует GroupBy со строковым ключом для реализации последовательности Distinct.(Из-за этого трюка списки, содержащие элементы с запятыми, могут работать неправильно.) В рабочем коде я бы использовал Distinct с IEqualityComparer для последовательностей, основанных на SequenceEqual.Он также имеет отдельный шаг для поиска максимальной длины повторяемой последовательности и затем для нахождения всех совпадающих последовательностей, в производственном коде я использовал бы расширение MaxBy.

Обновление: поскольку я использовал GroupBy для DistinctBy, я понял, что могу просто использовать это для подсчета повторов подпоследовательности, а не для их поиска. 

var repeaters = Enumerable.Range(0, words.Count) // starting positions
                       .SelectMany(n => Enumerable.Range(1, (words.Count - n) / 2).Select(l => words.Skip(n).Take(l).ToList())) // subseqs from each starting position
                       .GroupBy(s => String.Join(",", s), (k, sg) => new { seq = sg.First(), Repeats = sg.Count() }) // count each sequence
                       .Where(sr => sr.Repeats > 1) // only keep repeated sequences
                       .Select(sr => sr.seq); // no longer need counts
var maxRepeaterLen = repeaters.Select(ss => ss.Count()).Max(); // find longest repeated sequence's length
var maxLenRepeaters = repeaters.Where(ss => ss.Count() == maxRepeaterLen); // return all sequences matching longest length
0 голосов
/ 29 марта 2019

Попробуйте: 

List<int> words = new List<int> { 1, 2, 1, 2, 1, 2, 3, 2, 1, 2 };

string result =
    words
        .Select((c, i) => i)
        .SelectMany(i => Enumerable.Range(1, words.Count - i).Select(j => words.Skip(i).Take(j)), (i, w) => new { i, w })
        .GroupBy(x => String.Join(",", x.w), x => x.i)
        .Where(x => x.Skip(1).Any())
        .Select(x => x.Key)
        .OrderByDescending(x => x.Length)
        .First();

Это дает мне 1,2,1,2.

Если вы хотите тот, который действительно работает со строками, попробуйте это: 

var word = "supercalifragilisticexpialidocious";

string result =
    word
        .Select((c, i) => i)
        .SelectMany(i => Enumerable.Range(1, word.Length - i).Select(j => word.Skip(i).Take(j)), (i, w) => new { i, w })
        .GroupBy(x => new string(x.w.ToArray()), x => x.i)
        .Where(x => x.Skip(1).Any())
        .Select(x => x.Key)
        .OrderByDescending(x => x.Length)
        .First();

Это дает мне ali.

Вот немного более понятная версия: 

var word = "supercalifragilisticexpialidocious";

string result =
(
    from i in Enumerable.Range(0, word.Length)
    from j in Enumerable.Range(1, word.Length - i)
    group i by word.Substring(i, j) into gis
    where gis.Skip(1).Any()
    orderby gis.Key.Length descending
    select gis.Key
).First();
...