- Задача с форума
- Попробуем обобщить
Задача с форума
Недавно на форуме попался достаточно простой вопрос - как получить длину самой длинной последовательности чисел, идущих подряд (то есть где каждое последующее число диапазона больше предыдущего на единицу). Решение задачи достаточно простое и обсуждать тут особенно нечего, но я задался вопросом, как это сделать средствами LINQ, причем без использования свертки, иначе там логика была примерно такой же, что и при решении циклами. Там я выложил вот такое решение этой задачи| C# | 1
2
3
4
| 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); |
|
Первоначальный вариант выглядел так| C# | 1
2
3
4
| 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 удаляем нули.
Теперь нам надо разобраться, что же мы имеем на данном этапе и что нам это дает. Представим себе, что в исходной булевой коллекции у нас есть следующая последовательность где-то в середине этой коллекции.
| Code | 1
| false true true true false |
|
| Code | 1
2
3
4
5
| false 6
true 7
true 8
true 9
true 10 |
|
И после удаления нулей останется толькоТеперь, если мы найдем разность между этими соседними элементами (10 - 6 = 4), то в результате у нас получится число, на единицу большее, чем количество удаленных true из этого места, что в точности соответствует количеству элементов последовательности первоначальной коллекции. Таким образом, мы получили коллекцию таких чисел, что найдя разность между соседними элементами этой коллекции мы будем получать длину одного из диапазонов исходной коллекции. Соответсвнно, для получения списка длин, нам снова надо объединить попарно соседние элементы этой коллекции уже знакомым нам способом (Zip + Skip), вычисляя разности в результирующей функции, и найти максимум полученной коллекции разностей.
В приведенном выше коде есть пара нюансов, способных в некоторых случаях привести к ошибке. - Искомая последовательность может оказаться вначале или в конце исходной коллекции. Таким образом булева коллекция будет начинаться (или заканчиваться) с последовательности true, которые будут впоследствии удалены бесследно. Мало того, коллекции может полностью состоять из одного непрерывного диапазона, который даст коллекцию, состоящую полностью из true и она в следующем шаге будет полностью отфильтрована. Для того, чтобы избежать, после получения булевой коллекции ее надо с обеих сторон обрамить элементами false, поскольку именно они после фильтрации будут служить опорными точками. Кроме того, следует учесть, что первый false будет иметь индекс 0, так что при удалении нулей мы его потеряем вместе со всеми true. Чтобы этого избежать, нам надо либо вначале добавить два false, либо вместо нуля для замены использовать отрицательное число и удалять тоже именно его (в итоге я использовал -1).
- Если этот код оформить в виде отдельного метода, то будет совсем не лишним предусмотреть вариант, когда методу передается пустая коллекция или коллекция, состоящая из одного элемента.
То есть в итоге мы получим следующее:| C# | 1
2
3
4
5
6
7
8
9
10
| 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>, который будет выполнять эту задачу. Единственное, с чем нам нужно определиться, это с критерием, по которому мы будем определять, где заканчивается один диапазон и начинается другой. Обычно в диапазоне соседние элементы как-то связаны, например, в задаче выше, для того, чтобы элемент входил в тот же диапазон, что и предыдущий элемент, он должен быть на единицу больше его. То есть в качестве аргумента нашего метода мы можем использовать делегат, который будет принимать два соседних элемента коллекции и возвращать булево значение, которое будет показывать, входят эти элементы в один диапазон или в разные. То есть нам нужно реализовать метод со следующей сигнатурой.
| C# | 1
2
3
4
| public static IEnumerable<IEnumerable<T>> SplitByRanges<T>(this IEnumerable<T> ie, Func<T, T, bool> condition)
{
} |
|
| C# | 1
2
3
4
5
| var indecies = ie
.Zip(ie.Skip(1), condition)
.Concat(new bool[] { false })
.Select((item, index) => item ? -1 : index + 1)
.Where(i => i > -1); |
|
Теперь нам надо определиться с тем, как мы будем делить одну коллекцию на коллекцию коллекций. Как уже ранее говорилось, решить задачу надо без использования циклов, свертки и рекурсии, поэтому надо решение свести к использованию функций, которые могут дать в результате объект такого типа. Я решил использовать для этих целей GroupBy. В результате получился следующий код.| C# | 1
2
3
4
5
6
7
8
9
10
11
12
13
| 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));
} |
|
Тестируем метод следующим образом.| C# | 1
2
3
4
5
6
7
8
9
| 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();
} |
|
| Code | 1
2
3
4
5
6
7
| 1 2 3
5 6 7 8
3
3 4 5 6 7 8 9
1
1
1 |
|
| C# | 1
| Console.WriteLine(aaa.SplitByRanges((x, y) => y - x == 1).Select(i => i.Count()).Max()); |
|
|
