CODEWITHSUNDEEP
c#.netlinq
Contango
Contango

Reputation: 80342

Is it possible to use LINQ to check if all numbers in a list are increasing monotonically?

I'm interested if there is a way, in LINQ, to check if all numbers in a list are increasing monotonically?

Example

List<double> list1 = new List<double>() { 1, 2, 3, 4 };
Debug.Assert(list1.IsIncreasingMonotonically() == true);

List<double> list2 = new List<double>() { 1, 2, 100, -5 };
Debug.Assert(list2.IsIncreasingMonotonically() == false);

The reason I ask is that I would like to know the technique to compare an element in a list against its previous element, which is something I've never understood when using LINQ.

Finished Example Class in C#

As per official answer from @Servy below, here is the complete class I am now using. It adds extension methods to your project to check if a list is increasing/decreasing either monotonically, or strictly monotonically. I'm trying to get used to a functional programming style, and this is a good way to learn.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MyHelper
{
    /// <summary>
    /// Classes to check if a list is increasing or decreasing monotonically. See:
    /// http://stackoverflow.com/questions/14815356/is-it-possible-to-use-linq-to-check-if-all-numbers-in-a-list-are-increasing-mono#14815511
    /// Note the difference between strictly monotonic and monotonic, see:
    /// http://en.wikipedia.org/wiki/Monotonic_function
    /// </summary>
    public static class IsMonotonic
    {
        /// <summary>
        /// Returns true if the elements in the are increasing monotonically.
        /// </summary>
        /// <typeparam name="T">Type of elements in the list.</typeparam>
        /// <param name="list">List we are interested in.</param>
        /// <returns>True if all of the the elements in the list are increasing monotonically.</returns>
        public static bool IsIncreasingMonotonically<T>(this List<T> list) where T : IComparable
        {
            return list.Zip(list.Skip(1), (a, b) => a.CompareTo(b) <= 0).All(b => b);
        }

        /// <summary>
        /// Returns true if the elements in the are increasing strictly monotonically.
        /// </summary>
        /// <typeparam name="T">Type of elements in the list.</typeparam>
        /// <param name="list">List we are interested in.</param>
        /// <returns>True if all of the the elements in the list are increasing monotonically.</returns>
        public static bool IsIncreasingStrictlyMonotonically<T>(this List<T> list) where T : IComparable
        {
            return list.Zip(list.Skip(1), (a, b) => a.CompareTo(b) < 0).All(b => b);
        }

        /// <summary>
        /// Returns true if the elements in the are decreasing monotonically.
        /// </summary>
        /// <typeparam name="T">Type of elements in the list.</typeparam>
        /// <param name="list">List we are interested in.</param>
        /// <returns>True if all of the the elements in the list are decreasing monotonically.</returns>
        public static bool IsDecreasingMonotonically<T>(this List<T> list) where T : IComparable
        {
            return list.Zip(list.Skip(1), (a, b) => a.CompareTo(b) >= 0).All(b => b);
        }

        /// <summary>
        /// Returns true if the elements in the are decreasing strictly monotonically.
        /// </summary>
        /// <typeparam name="T">Type of elements in the list.</typeparam>
        /// <param name="list">List we are interested in.</param>
        /// <returns>True if all of the the elements in the list are decreasing strictly monotonically.</returns>
        public static bool IsDecreasingStrictlyMonotonically<T>(this List<T> list) where T : IComparable
        {
            return list.Zip(list.Skip(1), (a, b) => a.CompareTo(b) > 0).All(b => b);
        }

        /// <summary>
        /// Returns true if the elements in the are increasing monotonically.
        /// </summary>
        /// <typeparam name="T">Type of elements in the list.</typeparam>
        /// <param name="list">List we are interested in.</param>
        /// <returns>True if all of the the elements in the list are increasing monotonically.</returns>
        public static bool IsIncreasingMonotonicallyBy<T>(this List<T> list, Func<T> x) where T : IComparable
        {
            return list.Zip(list.Skip(1), (a, b) => a.CompareTo(b) <= 0).All(b => b);
        }

        public static void UnitTest()
        {
            {
                List<double> list = new List<double>() { 1, 2, 3, 4 };
                Debug.Assert(list.IsIncreasingMonotonically<double>() == true);
                Debug.Assert(list.IsIncreasingStrictlyMonotonically<double>() == true);
                Debug.Assert(list.IsDecreasingMonotonically<double>() == false);
                Debug.Assert(list.IsDecreasingStrictlyMonotonically<double>() == false);
            }

            {
                List<double> list = new List<double>() { 1, 2, 100, -5 };
                Debug.Assert(list.IsIncreasingMonotonically() == false);
                Debug.Assert(list.IsIncreasingStrictlyMonotonically() == false);
                Debug.Assert(list.IsDecreasingMonotonically() == false);
                Debug.Assert(list.IsDecreasingStrictlyMonotonically() == false);
            }

            {
                List<double> list = new List<double>() {1, 1, 2, 2, 3, 3, 4, 4};
                Debug.Assert(list.IsIncreasingMonotonically() == true);
                Debug.Assert(list.IsIncreasingStrictlyMonotonically<double>() == false);
                Debug.Assert(list.IsDecreasingMonotonically() == false);
                Debug.Assert(list.IsDecreasingStrictlyMonotonically() == false);
            }

            {
                List<double> list = new List<double>() { 4, 3, 2, 1 };
                Debug.Assert(list.IsIncreasingMonotonically() == false);
                Debug.Assert(list.IsIncreasingStrictlyMonotonically<double>() == false);
                Debug.Assert(list.IsDecreasingMonotonically() == true);
                Debug.Assert(list.IsDecreasingStrictlyMonotonically() == true);
            }

            {
                List<double> list = new List<double>() { 4, 4, 3, 3, 2, 2, 1, 1 };
                Debug.Assert(list.IsIncreasingMonotonically() == false);
                Debug.Assert(list.IsIncreasingStrictlyMonotonically<double>() == false);
                Debug.Assert(list.IsDecreasingMonotonically() == true);
                Debug.Assert(list.IsDecreasingStrictlyMonotonically() == false);
            }
        }
    }
}

Upvotes: 10

Views: 5661

Answers (8)

user3089790
user3089790

Reputation: 

public static class EnumerableExtensions
{
    private static bool CompareAdjacentElements<TSource>(this IEnumerable<TSource> source,
        Func<TSource, TSource, bool> comparison)
    {
        using (var iterator = source.GetEnumerator())
        {
            if (!iterator.MoveNext())
                throw new ArgumentException("The input sequence is empty", "source");
            var previous = iterator.Current;
            while (iterator.MoveNext())
            {
                var next = iterator.Current;
                if (comparison(previous, next)) return false;
                previous = next;
            }
            return true;
        }
    }

    public static bool IsSorted<TSource>(this IEnumerable<TSource> source)
        where TSource : IComparable<TSource>
    {
        return CompareAdjacentElements(source, (previous, next) => previous.CompareTo(next) > 0);
    }

    public static bool IsSorted<TSource>(this IEnumerable<TSource> source, Comparison<TSource> comparison)
    {
        return CompareAdjacentElements(source, (previous, next) => comparison(previous, next) > 0);
    }

    public static bool IsStrictSorted<TSource>(this IEnumerable<TSource> source)
        where TSource : IComparable<TSource>
    {
        return CompareAdjacentElements(source, (previous, next) => previous.CompareTo(next) >= 0);
    }

    public static bool IsStrictSorted<TSource>(this IEnumerable<TSource> source, Comparison<TSource> comparison)
    {
        return CompareAdjacentElements(source, (previous, next) => comparison(previous, next) >= 0);
    }
}

Upvotes: 1

Timothy Shields
Timothy Shields

Reputation: 79531

Consider an implementation like the following, which enumerates the given IEnumerable only once. Enumerating can have side-effects, and callers typically expect a single pass-through if that's possible.

public static bool IsIncreasingMonotonically<T>(
    this IEnumerable<T> _this)
    where T : IComparable<T>
{
    using (var e = _this.GetEnumerator())
    {
        if (!e.MoveNext())
            return true;
        T prev = e.Current;
        while (e.MoveNext())
        {
            if (prev.CompareTo(e.Current) > 0)
                return false;
            prev = e.Current;
        }
        return true;
    }
}

Upvotes: 1

Colonel Panic
Colonel Panic

Reputation: 137672

Use a loop! It's short, fast and readable. With the exception of Servy's answer, most the solutions in this thread are unnecessarily slow (sorting takes 'n log n' time) .

// Test whether a sequence is strictly increasing.
public bool IsIncreasing(IEnumerable<double> list)
{
    bool initial = true;
    double last = Double.MinValue;
    foreach(var x in list)
    {
        if (!initial && x <= last)
            return false;

        initial = false;
        last = x;
    }

    return true;
}

Examples

  1. IsIncreasing(new List<double>{1,2,3}) returns True
  2. IsIncreasing(new List<double>{1,3,2}) returns False

Upvotes: 4

Oleks
Oleks

Reputation: 32343

By using an Enumerable.Aggregate method:

list1.Aggregate((a, i) => a > i ? double.MaxValue : i) != double.MaxValue;

Upvotes: 4

Matt Johnson-Pint
Matt Johnson-Pint

Reputation: 241693

Here is a one-liner that will work:

var isIncreasing = list.OrderBy(x => x).SequenceEqual(list);

Or if you're going for performance, here is a one-liner that will only traverse the list once, and quits as soon as it reaches an element out of sequence:

var isIncreasing = !list.SkipWhile((x, i) => i == 0 || list[i - 1] <= x).Any();

Upvotes: 5

Servy
Servy

Reputation: 203827

public static bool IsIncreasingMontonically<T>(List<T> list) 
    where T : IComparable
{
    return list.Zip(list.Skip(1), (a, b) => a.CompareTo(b) <= 0)
        .All(b => b);
}

Note that this iterates the sequence twice. For a List, that's not a problem at all, for an IEnumerable or IQueryable, that could be bad, so be careful before you just change List<T> to IEnumerable<T>.

Upvotes: 12

Tim Schmelter
Tim Schmelter

Reputation: 460208

If you want to check whether a list always is increasing from index to index:

IEnumerable<int> list = new List<int>() { 1, 2, 3, 4, 5, 6, 7, 10 };
bool allIncreasing = !list
    .Where((i, index) => index > 0 && list.ElementAt(index - 1) >= i)
    .Any();

Demo

But in my opinion a simple loop would be more readable in this case.

Upvotes: 1

CR41G14
CR41G14

Reputation: 5594

Would you not order the list using OrderBy() and compare them against the original? If they are the same then it will give your your answer pseudo speaking:

var increasing = orignalList.OrderBy(m=>m.value1).ToList();
var decreasing = orignalList.OrderByDescending(m=>m.value1).ToList();

var mono = (originalList == increasing || originalList == decreasing)

Upvotes: 6

Related Questions