什麼是一個好的算法來檢查給定的值列表是否交替出現和下降？

Question

假設該函數需要一個double列表和一個索引來執行檢查，我需要檢查這些值是否連續上下交替。

例如，[14.0,12.3,13.0,11.4]的列表連續交替，但[14.0,12.3,11.4,13.0]的列表不交替。

的算法並不一定要快，但我想它是緊湊寫（LINQ是完全正常）。這是我目前的方法，它看起來太粗合我的口味：

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; 
    } 

Answer 1

我有一對夫婦連續拉鍊的，在擴展方法捆綁做到這一點：

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); 
    } 
} 

編輯：爲了完整，這裏是你如何使用功能：

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 

我也改變了實現方式，以更多的類型工作，儘可能地使用泛型。

Answer 2

您可以先創建樣的簽署數組：

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

這給你類似

列表

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

現在，您可以採取類似的appraoch作爲previos Select語句來檢查，如果一個-1遵循1：

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

現在result如果您的列表交替，則爲true;否則爲false。

編輯：爲確保在第二個查詢中的第一個檢查也通過在第二個查詢之前添加previous = -sign[0];。

Answer 3

假設在連續兩個相等的值是不能接受的（如果它們是，只是跳過相等的值）：

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; 

Answer 4

這裏是一個小的僞代碼。假設沒有重複的元素（可以很容易地通過很少的調整來處理）

想法是有一個sign變量交替1，-1，...，這個變量由兩個連續對的差值倍增，差異倍數通過這個sign變量必須總是正數。如果不是這樣，請返回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 

Answer 5

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); 
} 

Answer 6

試試這個：

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

的理念是：
如果值定的名單上下交替，數學就意味着它的衍生保持改變它的標誌。 所以這正是這段代碼所做的：

1. 獲得衍生產品。
2. 檢查符號波動。

而且獎勵是它不會評估所有衍生/跡象數組，除非有必要。