CODEWITHSUNDEEP
c#algorithmlinq
Xiagua
Xiagua

Reputation: 395

What's a good algorithm for checking if a given list of values alternates up and down?

Assuming the function takes in a list of double and an index to perform the check from, I need to check if the values alternates up and down consecutively.

For example, a list of [14.0,12.3,13.0,11.4] alternates consecutively but a list of [14.0,12.3,11.4,13.0] doesn't.

enter image description here

The algorithm doesn't have to be fast, but I'd like it to be compact to write (LINQ is totally fine). This is my current method, and it looks way too crude to my taste:

    enum AlternatingDirection { Rise, Fall, None };
    public bool CheckConsecutiveAlternation(List<double> dataList, int currDataIndex)
    {
        /*
         * Result True  : Fail
         * Result False : Pass
         */

        if (!_continuousRiseFallCheckBool)
            return false;

        if (dataList.Count < _continuousRiseFallValue)
            return false;

        if (currDataIndex + 1 < _continuousRiseFallValue)
            return false;

        AlternatingDirection direction = AlternatingDirection.None;
        int startIndex = currDataIndex - _continuousRiseFallValue + 1;
        double prevVal = 0;
        for (int i = startIndex; i <= currDataIndex; i++)
        {
            if (i == startIndex)
            {
                prevVal = dataList[i];
                continue;
            }

            if (prevVal > dataList[i])
            {
                prevVal = dataList[i];
                switch (direction)
                {
                    case AlternatingDirection.None:
                        direction = AlternatingDirection.Fall;
                        continue;
                    case AlternatingDirection.Rise:
                        direction = AlternatingDirection.Fall;
                        continue;
                    default:
                        //Two falls in a row. Not a signal.
                        return false;
                }
            }
            if (prevVal < dataList[i])
            {
                prevVal = dataList[i];
                switch (direction)
                {
                    case AlternatingDirection.None:
                        direction = AlternatingDirection.Rise;
                        continue;
                    case AlternatingDirection.Fall:
                        direction = AlternatingDirection.Rise;
                        continue;
                    default:
                        //Two rise in a row. Not a signal.
                        return false;
                }
            }
            return false;
        }

        //Alternated n times until here. Data is out of control.
        return true;
    }

Upvotes: 1

Views: 319

Answers (6)

Tomas Aschan
Tomas Aschan

Reputation: 60634

I'd do it with a couple of consecutive zips, bundled in an extension method:

public static class AlternatingExtensions {
    public static bool IsAlternating<T>(this IList<T> list) where T : IComparable<T>
    {
        var diffSigns = list.Zip(list.Skip(1), (a,b) => b.CompareTo(a));
        var signChanges = diffSigns.Zip(diffSigns.Skip(1), (a,b) => a * b < 0);
        return signChanges.All(s => s);
    }
}

Edit: for completeness, here's how you'd use the feature:

 var alternatingList = new List<double> { 14.0, 12.3, 13.0, 11.4 };
 var nonAlternatingList = new List<double> { 14.0, 12.3, 11.4, 13.0 };
 alternatingList.IsAlternating(); // true
 nonAlternatingList.IsAlternating(); // false

I also changed the implementation to work on more types, making use of generics as much as possible.

Upvotes: 1

Avi Turner
Avi Turner

Reputation: 10456

Try this:

public static bool IsAlternating(double[] data)
{
    var d = GetDerivative(data);

    var signs = d.Select(val => Math.Sign(val));

    bool isAlternating =
   signs.Zip(signs.Skip(1), (a, b) => a != b).All(isAlt => isAlt);

    return isAlternating;
}

private static IEnumerable<double> GetDerivative(double[] data)
{
    var d = data.Zip(data.Skip(1), (a, b) => b - a);
    return d;
}

Live demo

The idea is:
If the given list of values is alternating up and down, mathematically it means that it's derivative keeps changing its sign. So this is exactly what this piece of code does:

  1. Get the derivative.
  2. Checks for sign fluctuations.

And the bonus is that it will not evaluate all of the derivative / signs arrays unless it is necessary.

Upvotes: 3

MakePeaceGreatAgain
MakePeaceGreatAgain

Reputation: 37050

You may create kind of a signed array first:

double previous = 0;
var sign = myList.Select(x => {
    int s = Math.Sign(x - previous);
    previos = x;
    return s;
});

This gives you a list similar to 

{ -1, 1, -1, ... }

Now you can take a similar appraoch as the previos Select-statement to check if a -1 follows a 1:

var result = sign.All(x => {
    bool b = x == -previous;
    previous = x;
    return b;
});

Now result is true if your list alternates, false otherwise.

EDIT: To ensure that the very first check within the second query also passes add previous = -sign[0]; before the second query.

Upvotes: 1

Aidan Connelly
Aidan Connelly

Reputation: 184

public double RatioOfAlternations(double[] dataList)
{
    double Alternating = 0;
    double Total = (dataList.Count()-2);
    for (int (i) = 0; (i) < Total; (i)++)
    {
        if (((dataList[i+1]-dataList[i])*(dataList[i+2]-dataList[i+1]))<0) 
// If previous change is opposite sign to current change, this will be negative
        {
            Alternating++;
        }
        else
        {
        }
    }
    return (Alternating/Total);
}

Upvotes: 0

amit
amit

Reputation: 178491

Here is a small pseudo code. Assuming no repeated elements (can be handled easily though by few tweaks)

Idea is to have a sign variable which is alternating 1,-1,... that is multipled by the difference of two consecutive pairs, the difference multipled by this sign variable must always be positive. If it's not at some point, return false.

isUpAndDown(l):
   if size(l) < 2: // empty,singleton list is always good.
      return true
   int sign = (l[0] < l[1] ? 1 : -1) 
   for i from 0 to n-1 (exclusive):
       if sign * (l[i+1] - l[i]) < 0:
          return false //not alternating
       sign = sign * -1
   end for
   return true //all good

Upvotes: 1

Aasmund Eldhuset
Aasmund Eldhuset

Reputation: 37960

Assuming that two equal values in a row are not acceptable (if they are, just skip over equal values):

if (dataList[0] == dataList[1])
    return false;
bool nextMustRise = dataList[0] > dataList[1];
for (int i = 2; i < dataList.Count; i++) {
    if (dataList[i - 1] == dataList[i] || (dataList[i - 1] < dataList[i]) != nextMustRise)
        return false;
    nextMustRise = !nextMustRise;
}
return true;

Upvotes: 0

Related Questions