假設我有一個值列表：[0, 10, 20, 10, 0, 10, 20, 10, 0, ...]顯然有周期性。我們看到每5個條目就有一個循環。我想測量上面列表中的平均周期，或完成一個周期所需的平均條目數。這似乎類似于測量自相關，但我不知道從哪里開始獲得某種“頻率”或“周期性”的測量值，也就是一個周期完成的速度。
5 回答
慕桂英3389331
TA貢獻2036條經驗 獲得超8個贊
最小版本：
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]
慕無忌1623718
TA貢獻1744條經驗 獲得超4個贊
啟動一個空列表
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)
應該適用于幾乎任何情況，將間隔作為輸出提供給您。
守著一只汪
TA貢獻1872條經驗 獲得超4個贊
“純”平均周期必然等于列表的長度除以元素的出現次數。
我們還可以考慮第一次和最后一次出現，并在我們的計算中使用它，盡管這可能會以您不希望的方式影響您的計算：
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
}
慕虎7371278
TA貢獻1802條經驗 獲得超4個贊
這是解決此問題的一種方法。基本上，您從 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
catspeake
TA貢獻1111條經驗 獲得超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
添加回答
舉報
0/150
提交
取消