Let's say I have a list of values: [0, 10, 20, 10, 0, 10, 20, 10, 0, ...]
Clearly there's periodicity. We see that there is a cycle every 5 entries. I want to measure the average periodicity, or the average number of entries it takes to complete a cycle, within the list above.
This seems similar to measuring autoocorrelation but I don't know where to begin to get some sort of measure of the "frequency" or "periodicity", aka how fast a cycle is completed.
On
The "pure" average periodicity will necessarily be equivalent to the length of the list divided by the count of occurrences of an element.
We can also account for first and last appearances, and use that in our calculation, although this may affect you calculation in ways that you might not want:
from collections import Counter
values = [0, 10, 20, 10, 0, 10, 20, 10, 0]
counts = Counter(values)
periodicities = dict()
r_values = values[::-1]
for k, v in counts.items():
print(r_values.index(k), values.index(k))
periodicities[k] = (len(values) - r_values.index(k) - values.index(k) + 1) / v
print(periodicities)
Result:
{
0: 3.3333333333333335,
10: 2.0,
20: 3.0
}
a=[0, 10, 20, 10, 0, 10, 20, 10, 0, 10, 20]
n=len(a)
# The idea is to compare the repeated subset of the array with the original array
# while keeping the sizes equal
periods = [i for i in range(2,n//2+1) if a[:i]*(n//i)==a[:n - n % i]]
print('Min period=',periods[0], '\n',a[:periods[0]])
Output:
Min period: 4
[0, 10, 20, 10]
Here is the same idea with for-loop just to make it more clear:
a=[0, 10, 20, 10, 0, 10, 20, 10, 0, 10, 20]
n = len(a)
periods=[]
for i in range(2, n // 2 + 1): # cycle's max length = 1/2 of sequence
m = n // i
word = a[:i]
repeated_word = [a[:i]*m][0]
same_size_array = a[:len(repeated_word)]
isCycle = repeated_word == same_size_array
if isCycle:
periods.append(i)
print(
'%s-char word\t' % i,word,
'\nRepeated word\t',repeated_word,
'\nSame size array\t',same_size_array,
'\nEqual(a Cycle)?\t',isCycle
,'\n'
)
period = periods[0] # shortest cycle
print('Min period:',period,'\n',a[:period])
Output (long version):
2-char word [0, 10]
Repeated word [0, 10, 0, 10, 0, 10, 0, 10, 0, 10]
Same size array [0, 10, 20, 10, 0, 10, 20, 10, 0, 10]
Equal(a Cycle)? False
3-char word [0, 10, 20]
Repeated word [0, 10, 20, 0, 10, 20, 0, 10, 20]
Same size array [0, 10, 20, 10, 0, 10, 20, 10, 0]
Equal(a Cycle)? False
4-char word [0, 10, 20, 10]
Repeated word [0, 10, 20, 10, 0, 10, 20, 10]
Same size array [0, 10, 20, 10, 0, 10, 20, 10]
Equal(a Cycle)? True
5-char word [0, 10, 20, 10, 0]
Repeated word [0, 10, 20, 10, 0, 0, 10, 20, 10, 0]
Same size array [0, 10, 20, 10, 0, 10, 20, 10, 0, 10]
Equal(a Cycle)? False
Min period: 4
[0, 10, 20, 10]
Note: I'm assuming you're referring to exact periodicity rather than some measure of autocorrelation. E.g., [1, 5, 8, 1, 5, 8.0000000001] would have a period of 6 rather than 3.
This is by no means optimal, but in a pinch anyone can brute force a solution that looks something like the following.
def period(L):
n = len(L)
for i in range(1, n):
if n%i:
# save a little work if `i` isn't a factor of `n`
continue
if all(L[k:k+i]==L[:i] for k in range(0, n, i)):
# `L` is just `L[:i]*x` for some `x`, and since `i` is
# increasing this must be the smallest `i` where that
# is true
return i
# if no factor suffices, the smallest generator is the entire list
return n
With a little more effort we can get linear performance rather than quadratic. Optimizing it further is left as an exercise for somebody who isn't me.
def period(L):
if not L:
return 0
guess = 1
for i, x in enumerate(L[1:], 1):
if x != L[i%guess]:
"""
We know for certain the period is not `guess`. Moreover, if we've
gotten this far we've ruled out every option less than `guess`.
Additionally, no multiple of `guess` suffices because the fact
that `L` consists of repetitions of width `guess` up till now means
that `i%(t*guess)!=x` for any `t` so that `t*guess<i`. Interestingly,
that's the precisely the observation required to conclude
`guess >= i+1`; there is some positive integer multiple of `guess`
so that `L[:i+1]` consists of a copy of that width and some number
of elements that are identical to that copy up to and excluding `x`.
Since `L[:i+1]` has that structure, no width between that multiple
of `guess` and `i` can generate `L`. Hence, the answer is at least
`i+1`.
"""
guess = i+1
while len(L)%guess:
"""
Additionally, the answer must be a factor of `len(L)`. This
might superficially look quadratic because of the loop-in-a
-loop aspect to it, but since `1<=guess<=len(L)` and `guess`
is always increasing we can't possibly run this code more
than some linear number of times.
"""
guess += 1
"""
If we've gotten this far, `guess` is a factor of `L`, and it is
exactly as wide as all the elements we've seen so far. If we
continue iterating through `L` and find that it is just a bunch
of copies of this initial segment then we'll be done. Otherwise,
we'll find ourselves in this same if-statement and reset our
`guess` again.
"""
return guess
If you want all periods, then those are simply every multiple of the minimum period which are also factors of the total length. Supposing you have a way to compute the prime factorization or all positive factors (including 1 and the integer itself) of a positive integer, the following routine can get you those. Actually finding the factors of an integer is probably out of scope and is well-answered elsewhere.
def all_periods(minimum_period, collection_size):
p, n = minimum_period, collection_size
if p==0:
yield = 0
return
for f in positive_factors(n / p):
yield f * p
Here is one way to approach this problem. Basically, you iterate from 2 to len(lst)//2 + 1 and check if the first n elements matches every next n elements, return n if true. If no match is found, return len(lst)
def get_periodicity(lst):
t = len(lst)
for n in range(2, t//2 + 1):
for p in range(1, t//n):
if lst[:n] != lst[n*p:n*p+n]:
break
else:
rem = t%n
if not rem or lst[-rem:] == lst[:rem]:
return n
else:
return t
Tests
>>> get_periodicity([0, 10, 20, 10, 0, 10, 20, 10, 0, 10, 20])
4
>>> get_periodicity([1,1,2,1,1,2,1,1,2,1,1,2])
3
>>> get_periodicity([1,1,2,1,1,2,1,1,2,1,1,2,3])
13
Initiate an empty list
interval = []and use a recursive function, like so:
OPTIMIZED CODE ONLY, WITHOUT COMMENTS
To do what you want, simply run your function after initiating []
should work for pretty much any case, delivering you the interval as output.