How to check if a sequence of numbers has a increasing/decreasing trend in C++

Question

What's the best way to check if a sequence of numbers has an increasing or decreasing trend?

I know that I could pick the first and last value of the sequence, and check their difference, but I'd like a somewhat more robust check. This means that I want to be able to tolerate a minority of increasing values within a mostly decreasing sequence, and viceversa.

More specifically, the numbers are stored as

vector<int> mySequence;

A few more details about the number sequences that I am dealing with:

• All the numbers within the sequence have the same order of magnitude. This means that no sequence like the following can appear: [45 38 320 22 12 6].
• By descending trend I mean that most or all the numbers within the sequence are lesser than the previous one. (The opposite applies for ascending trend). As a consequence, the following sequence is to be considered as descending: [45 42 38 32 28 34 26 20 12 8 48]

Sarson

Could you give an example of a sequence where the first value is greater than the last value and yet you would consider the sequence to be increasing? That doesn't really make sense to me. – Fransen

Would your sequence still be descending if instead of 34 you had, say, 200? ie. do the sizes matter or are you just comparing the left number with its right number for all numbers? – Obsession

For this to be a programming question, you would have to specify your algorithm to determine whether the sequence is increasing/decreasing, then try to implement it, then ask a question if you have any problems. – Edington

Note that this question is not about C++, but about defining "trend". – Zwinglian

@frickshit the input values are never out-of scale with the rest of the values. – Sarson

The proposed edit still doesn't define "trend" mathematically speaking. "Most or all" doesn't mean anything. In your example, starting after 26, it is not "lesser than the previous ones". So half of your serie is not descending. So indeed you mean "most or all the numbers are lesser than most or all the previous ones" and it just has no sense mathematically speaking. Ask yourself what you want to achieve and find a better definition (with words like linear extrapolation, majority, percentile, etc...) that deals with all exceptions (last/first/middle number is high...). – Heraldic

Answer 1

I would accumulate the number of increases vs number of decreases, which should give you an idea of whether there's an overall trend to increase or decrease.

Modestomodesty

I see to variants here. 1) Accumulate the difference of each number with the strarting value. 2) Accumulate the difference of each sequential pair. What could be the best option? – Sarson

This is a good and fast way of finding out the overall trend. Only O(n), better than ordering and finding the median or other expensive suggestions. – Bifocals

If it needs to be even more failure-proof, do this on a running average calculated from the original data set. That way you can prevent malicious sequences like +10 -1 -1 +8 -1 +9 -1 +12 -2 -1 from coming out at "decreasing" when in fact they're increasing. – Daydream

The first option (Accumulate the difference of each number with the starting value.) could be dangerous, since if would fail in case the first value is a "misleading" one (too high, or too low). – Expositor

Answer 2

You probably could look into trend estimation and some type of regression like linear regression.

It depends of course on the specific application of yours, but in general it sounds like a fitting problem.

Carmacarmack

This would not work if there is one element in the sequence that is huge -- it is important to know whether the size of the numbers matters for the trend here. – Obsession

@frickskityes, you are right that it is important to understand the specific application i.e. if outliers matter or not. – Carmacarmack

The input values do not contain out-of-scale huge values, I'm currently checking out the two linked resources to find the best option. I'm actually thinking about running my check on a sequence generated by running a local average on the original sequence, as suggested by @Damon. – Sarson

Answer 3

I think you can simply calculate the median of your sequence and check if it is greater than the first value.
This is ONE way, not THE way.

Another way, always considering average medium, you can check the number of ascending and descending values in the sequence.

int trend = 0;
int avg = mySequence[0]; 
int size = mySequence.size();
for (int i=0; i < size - 1; ++i) {
  if(i > 0) { 
   avg = (avg + mySequence[i]) / 2; 
  }
  (mySequence[i+1] - avg) > 0 ? ++trend; --trend;    
}

Fukuoka

Answer 4

One possibility would be to count the number of ascending and descending values in the sequence:

int trend = 0;
for (int i=0;i<mySequence.size()-1;++i)
{
    diff = mySequence[i+1] - mySequence[i];
    if (diff > 0)
    {
       trend++;
    }
    else if (diff < 0)
    {
       trend--;
    }
}

The sequence you give in example will end with trend equal to -6

Elayneelazaro

Answer 5

I would most probably try to split the sequence into multiple segments, as you said the values do not differ dramatically - see piecewise regression and to interpret the segments as your business needs.

You will need a vector for storing the segments, each segment having start/end index, some sort of median value, etc - see also where to split a piecewise regression

Reflector

Answer 6

I suggest using methods from mathematical analysis (e.g. integral and differential calculus) applied to discrete integer sequences.

One way is then to compute rolling averages and see if those averages increase or decrease. Natural and easy ;)

Disqualify