algorithmsliding

The number of a sliding window for each element in the list of number?


Let L be a list of numbers as [7,9,0,3,5,2]. When creating a sliding windows of stride 1 and size 3 I have the following windows :

(7,9,0) (9,0,3) (0,3,5) (3,5,2).

My question is if there is a simple formula to give the number of windows for each position in L ?

For example : If we note N the length of L and M the size of the sliding window, we have this formula to get the total number of windows N-M+1

But I'm looking for another formula like f(i) where i is the position : f(1)=1, f(2)=2,f(3)=3, f(4)=2,f(5)=1


Solution

  • For given:

    Then the pseudo code for getting that count in constant time is:

    get_count(n, stride, size, k):
        return max(0, 1 + min(k, n - size) / stride - max(0, k - size + stride) / stride);
    

    ... where integer division is intended. So for example, in JavaScript syntax:

    function getCount(n, stride, size, k) {
        return Math.max(0, 1 + Math.floor(Math.min(k, n - size) / stride) 
                             - Math.floor(Math.max(0, k - size + stride) / stride));
    }