假设我有一个值列表： [0, 10, 20, 10, 0, 10, 20, 10, 0, ...]
显然有周期性。我们看到每 5 个条目有一个循环。我想在上面的列表中测量平均周期性，或完成一个周期所需的平均条目数。
这似乎类似于测量自相关，但我不知道从哪里开始测量“频率”或“周期性”，也就是完成一个周期的速度。
问问题
380 次
5 回答
1
最小版本：
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]])
输出：
Min period: 4
[0, 10, 20, 10]
for循环版本：
这是与 for-loop 相同的想法，只是为了使其更清晰：
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])
输出（长版）：
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]
于 2020-07-31T03:09:43.280 回答
0
注意：我假设您指的是确切的周期性，而不是某种自相关度量。例如，[1, 5, 8, 1, 5, 8.0000000001]周期为 6 而不是 3。
这绝不是最优的，但在紧要关头，任何人都可以暴力破解一个看起来像下面这样的解决方案。
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
稍加努力，我们可以获得线性性能而不是二次性能。进一步优化它留给不是我的人作为练习。
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
如果您想要所有周期，那么这些只是最小周期的每个倍数，它们也是总长度的因素。假设您有一种方法可以计算正整数的素数分解或所有正因数（包括 1 和整数本身），以下例程可以为您提供这些。实际上找到整数的因子可能超出了范围，并且在其他地方得到了很好的回答。
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
于 2020-07-31T03:31:04.370 回答
0
启动一个空列表
interval = []
并使用递归函数，如下所示：
def check_for_interval(interval,list):
## step 1: add first list element into your interval
interval.append(list[0])
## step 2: remove that element from your list
list.pop(0)
## step 3: get the current content of your interval, plus the next
## element, and check if the concatenated content appears another time
## in the source list.
## first, make sure you got only strings in your list, for join to work
str_interval = []
for y in interval:
str_interval.append(str(y))
## attach the next element, which now is the first one of the list
## because you popped the "new" first one above
str_interval.append(str(list[0]))
## next, concatenate the list content as string, like so:
current_interval = ",".join(str_interval)
## now, transform the current remaining list (except the "new" first
## element cause added in your test string above) into a string of the
## exact same structure (elements separated by commas)
str_test = []
list_test = list[1:]
for z in list_test:
str_test.append(str(z))
## next,concatenate the list content as string, like so:
remaining_elements = ",".join(str_test)
## finally, check if the current_interval is present inside the
## remaining_elements. If yes
if remaining_elements.find(current_interval) != -1:
## check if the amount of remaining elements is equal to the amount
## of elements constituting the interval -1 at the moment, OR if the
## current_interval is found in the remaining elements, its
## starting index is equal to 0, and the len of str_test is a pair
## entire multiple of str_interval
check_list_test = remaining_elements.split(",")
check_list_interval = current_interval.split(",")
if (len(str_interval) == len(str_test)) or (remaining_elements.find(current_interval) == 0 and len(str_test) % len(str_interval) == 0 and (len(str_test) / len(str_interval)) % 2 == 0 and (len(check_list_test) / len(check_list_interval)) * check_list_interval == check_list_test):
## If yes, attach the "new" first element of the list to the interval
## (that last element was included in str_interval, but is not yet
## present in interval)
interval.append(list[0])
## and print the output
print("your interval is: " + str(interval))
else:
## otherwise, call the function recursively
check_for_interval(interval,list)
else:
## when the current interval is not found in the remaining elements,
## and the source list has been fully iterated (str_test's length
## == 0), this also means that we've found our interval
if len(str_test) == 0:
## add the last list element into the interval
interval.append(list[0])
print("your interval is: " + str(interval))
else:
## In all other cases, again call the function recursively
check_for_interval(interval,list)
仅优化代码，无评论
def int_to_str_list(source):
new_str_list = []
for z in source:
new_str_list.append(str(z))
return new_str_list
def check_for_interval(interval,list):
interval.append(list[0])
list.pop(0)
str_interval = int_to_str_list(interval)
str_interval.append(str(list[0]))
current_interval = ",".join(str_interval)
str_test = int_to_str_list(list[1:])
remaining_elements = ",".join(str_test)
str_exam = remaining_elements.find(current_interval)
if str_exam != -1:
interval_size = len(str_interval)
remaining_size = len(str_test)
rem_div_inter = remaining_size / interval_size
if (interval_size == remaining_size) or (str_exam == 0 and remaining_size % interval_size == 0 and rem_div_inter % 2 == 0 and rem_div_inter * str_interval == str_test):
interval.append(list[0])
print("your interval is: " + str(interval))
else:
check_for_interval(interval,list)
else:
if len(str_test) == 0 :
interval.append(list[0])
print("your interval is: " + str(interval))
else:
check_for_interval(interval,list)
要做你想做的事，只需在启动 [] 后运行你的函数
interval = []
check_for_interval(interval,list)
应该适用于几乎任何情况，将间隔作为输出提供给您。
于 2020-07-30T22:01:29.380 回答
0
“纯”平均周期性必然等于列表的长度除以元素的出现次数。
我们还可以考虑第一次和最后一次出现，并在我们的计算中使用它，尽管这可能会以您可能不希望的方式影响您的计算：
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)
结果：
{
0: 3.3333333333333335,
10: 2.0,
20: 3.0
}
于 2020-07-30T22:03:23.247 回答
0
这是解决此问题的一种方法。基本上，您从 2 迭代到len(lst)//2 + 1并检查前 n 个元素是否与接下来的 n 个元素匹配，如果为真则返回 n。如果未找到匹配项，则返回 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
测试
>>> 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
于 2020-07-31T09:23:31.477 回答