Разбиение коллекции на диапазоны средствами LINQ.

1. Задача с форума
2. Попробуем обобщить

Задача с форума

Недавно на форуме попался достаточно простой вопрос - как получить длину самой длинной последовательности чисел, идущих подряд (то есть где каждое последующее число диапазона больше предыдущего на единицу). Решение задачи достаточно простое и обсуждать тут особенно нечего, но я задался вопросом, как это сделать средствами LINQ, причем без использования свертки, иначе там логика была примерно такой же, что и при решении циклами. Там я выложил вот такое решение этой задачи

Код csharp

Выделить

            int[] ia = { 1, 0, -1, 2, 3, -2, 4, 5, 6, -3, -4, 7, 8, 9, 10, 11};
            var qqq = ia.Zip(ia.Skip(1), (i1, i2) => i2 - i1 == 1).Concat(new bool[] { false}).Select((b, i) => b ? 0 : i).Where(x => x > 0);
            var maxCount = qqq.Zip(qqq.Skip(1), (x, y) => y - x).Max();
            Console.WriteLine(maxCount);

Несмотря на то, что, как потом выяснилось, это решение в некоторых случаях не работает, тем не менее в конечном варианте логика останется такой же, а модификация кода будет незначительной. Учитывая, что данный код выглядит немного непонятно, думаю, дать пояснения по поводу того, что здесь происходит - будет совсем не лишним.
Первоначальный вариант выглядел так

Код csharp

Выделить

            int[] ia = { 1, 0, -1, 2, 3, -2, 4, 5, 6, -3, -4, 7, 8, 9, 10, 11, -4, 12, 13};
            var qqq = ia.Zip(ia.Skip(1), (i1, i2) => i2 - i1 == 1).Select((b, i) => b ? 0 : i).Where(x => x > 0);
            var maxCount = qqq.Zip(qqq.Skip(1), (x, y) => y - x).Max();
            Console.WriteLine(maxCount);

Это сработало правильно, одну проблему я заметил и исправил сразу, но сначала объясню на этом - немного более простом - примере, поскольку в окончательном варианте логика будет той же.

Для выявления диапазонов, в которых должны сравниваться соседние элементы здесь используется сочетание функций Zip и Skip. Первая объединяет две коллекции попрано, а вторая(переданная с аргументом 1) сдвигает элементы коллекции на одну позицию. Таким образом (поскольку источником обеих функций является одна и та же коллекция) мы объединяем первый элемент со вторым, второй с третьим и т. д. Второй аргумент функции Zip - проверяет, действительно ли элемент i2 больше элемента i1 на единицу. В результате такой операции мы получим булеву коллекцию, в которой каждый элемент будет указывать, относятся ли соответствующие ему соседние элементы исходной коллекции к одному диапазону (отличаются ли на единицу). Таким образом, если в каком-то месте исходной коллекции был диапазон из трех последовательных чисел, то в полученной нами коллекции на его месте будет диапазон из двух элементов true. Например диапазон 7 8 9 даст true для разницы между 7 и 8, и еще true для разницы 8 и 9.
Далее с помощью функции Select мы заменяем элементы true нулями, а false - их индексами в нашей булевой коллекции. После этого с помощью функции Where удаляем нули.
Теперь нам надо разобраться, что же мы имеем на данном этапе и что нам это дает. Представим себе, что в исходной булевой коллекции у нас есть следующая последовательность где-то в середине этой коллекции.

Код:

false true true true false

Наличие трех true подряд, как мы уже выяснили выше, означает, что в соответствующем фрагменте исходной коллекции мы имели четыре подряд идущих числа. Допуситм, что первый false имел индекс 6, тогда соответствующие индексы для этого фрагмента распределятся следующим образом

Код:

false 6
true 7
true 8
true 9
true 10

Теперь, если мы заменим true - нулями, а false - их индексами, мы получим последовательность

Код:

6 0 0 0 10

И после удаления нулей останется только

Код:

6 10

Теперь, если мы найдем разность между этими соседними элементами (10 - 6 = 4), то в результате у нас получится число, на единицу большее, чем количество удаленных true из этого места, что в точности соответствует количеству элементов последовательности первоначальной коллекции. Таким образом, мы получили коллекцию таких чисел, что найдя разность между соседними элементами этой коллекции мы будем получать длину одного из диапазонов исходной коллекции. Соответсвнно, для получения списка длин, нам снова надо объединить попарно соседние элементы этой коллекции уже знакомым нам способом (Zip + Skip), вычисляя разности в результирующей функции, и найти максимум полученной коллекции разностей.

В приведенном выше коде есть пара нюансов, способных в некоторых случаях привести к ошибке.

1. Искомая последовательность может оказаться вначале или в конце исходной коллекции. Таким образом булева коллекция будет начинаться (или заканчиваться) с последовательности true, которые будут впоследствии удалены бесследно. Мало того, коллекции может полностью состоять из одного непрерывного диапазона, который даст коллекцию, состоящую полностью из true и она в следующем шаге будет полностью отфильтрована. Для того, чтобы избежать, после получения булевой коллекции ее надо с обеих сторон обрамить элементами false, поскольку именно они после фильтрации будут служить опорными точками. Кроме того, следует учесть, что первый false будет иметь индекс 0, так что при удалении нулей мы его потеряем вместе со всеми true. Чтобы этого избежать, нам надо либо вначале добавить два false, либо вместо нуля для замены использовать отрицательное число и удалять тоже именно его (в итоге я использовал -1).
2. Если этот код оформить в виде отдельного метода, то будет совсем не лишним предусмотреть вариант, когда методу передается пустая коллекция или коллекция, состоящая из одного элемента.

То есть в итоге мы получим следующее:

Код csharp

Выделить

        static int MaxRangeLength(IEnumerable<int> ia)
        {
            if (ia.Count() < 2) return ia.Count();
            var qqq = new bool[] { false }
                .Concat(ia.Zip(ia.Skip(1), (i1, i2) => i2 - i1 == 1))
                .Concat(new bool[] { false })
                .Select((b, i) => b ? -1 : i)
                .Where(x => x > -1);
            return qqq.Zip(qqq.Skip(1), (x, y) => y - x).Max();
        }

Не могу сказать, что провел полноценное тестирование, но минимальные тесты метод прошел и дал хорошие результаты.

Попробуем обобщить

Описанная выше задача имела достаточно частный характер и, по всей видимости, нужна была только конкретному студенту. Однако же задача деления коллекции на диапазоны может иметь и прикладной характер, поэтому попробуем создать метод расширения для IEnumerable<T>, который будет выполнять эту задачу. Единственное, с чем нам нужно определиться, это с критерием, по которому мы будем определять, где заканчивается один диапазон и начинается другой. Обычно в диапазоне соседние элементы как-то связаны, например, в задаче выше, для того, чтобы элемент входил в тот же диапазон, что и предыдущий элемент, он должен быть на единицу больше его. То есть в качестве аргумента нашего метода мы можем использовать делегат, который будет принимать два соседних элемента коллекции и возвращать булево значение, которое будет показывать, входят эти элементы в один диапазон или в разные. То есть нам нужно реализовать метод со следующей сигнатурой.

Код csharp

Выделить

        public static IEnumerable<IEnumerable<T>> SplitByRanges<T>(this IEnumerable<T> ie, Func<T, T, bool> condition)
        {
 
        }

Теперь о реализации. Первая часть этого метода очень похожа на то, что мы делали выше. Мы получаем индексы границ диапазонов, причем нам достаточно получить верхние границы. Фактически мы будем получать список чисел, каждое из которых на единицу превышает индекс последнего элемента одного из диапазонов в исходной коллекции.

Код csharp

Выделить

            var indecies = ie
                .Zip(ie.Skip(1), condition)
                .Concat(new bool[] { false })
                .Select((item, index) => item ? -1 : index + 1)
                .Where(i => i > -1);

Здесь мы добавляем false только в конец булевой коллекции, поскольку нам надо вычислить только верхние границы диапазонов. Остальное более-менее понятно всем кто прочитал предыдущий пример.

Теперь нам надо определиться с тем, как мы будем делить одну коллекцию на коллекцию коллекций. Как уже ранее говорилось, решить задачу надо без использования циклов, свертки и рекурсии, поэтому надо решение свести к использованию функций, которые могут дать в результате объект такого типа. Я решил использовать для этих целей GroupBy. В результате получился следующий код.

Код csharp

Выделить

        public static IEnumerable<IEnumerable<T>> SplitByRanges<T>(this IEnumerable<T> ie, Func<T, T, bool> condition)
        {
 
            var indecies = ie
                .Zip(ie.Skip(1), condition)
                .Concat(new bool[] { false })
                .Select((item, index) => item ? -1 : index + 1)
                .Where(i => i > -1);
 
            return ie
                   .Select((item, index) => new { item, key = indecies.First(x => index < x) })
                   .GroupBy(x => x.key, (k, e) => e.Select(ee => ee.item));
        }

Здесь каждому элементу исходной коллекции сопоставляется ключ, получаемый следующим образом: в коллекции индексов находится самый первый индекс, превышающий индекс текущего элемента исходной коллекции и именно он и будет использоваться как ключ. Таким образом, если в коллекции индексов у нас есть числа 3 и 8, то элементы с индексами 0 1 2, получат ключ 3, а элементы с индексами 3 4 5 6 7, получат ключ 8 и т. д. Далее осуществляется группировка по этому ключу, а поскольку группируются объекты, содержащие элемент и ключ, то полученные группы надо преобразовать в коллекции элементов, для этого используется перегрузка GroupBy, включающая функцию-селектор.

Тестируем метод следующим образом.

Код csharp

Выделить

            int[] aaa = { 1, 2, 3, 5, 6, 7, 8, 3, 3, 4, 5, 6, 7, 8, 9, 1, 1, 1 };
            foreach (IEnumerable<int> aa in aaa.SplitByRanges((x, y) => y - x == 1))
            {
                foreach(int a in aa)
                {
                    Console.Write(a + " ");
                }
                Console.WriteLine();
            }

Здесь мы передали нашему методу функцию, которая отбирает в группы подряд идущие элементы(следующий на единицу больше предыдущего). На выходе получаем

Код:

1 2 3
5 6 7 8
3
3 4 5 6 7 8 9
1
1
1

Ну и теперь можно гораздо проще решить "задачу с форума"

Код csharp

Выделить

Console.WriteLine(aaa.SplitByRanges((x, y) => y - x == 1).Select(i => i.Count()).Max());