如何检测无限序列中的重复数字？我尝试了 Floyd＆Brent 检测算法，但一无所获…我有一个生成器，其生成的数字范围为0到9（含0）（包括0），并且我必须识别其中的一个句点。
示例测试用例：
import itertools # of course this is a fake one just to offer an example def source(): return itertools.cycle((1, 0, 1, 4, 8, 2, 1, 3, 3, 1)) >>> gen = source() >>> period(gen) (1, 0, 1, 4, 8, 2, 1, 3, 3, 1)
这是一个有趣的问题。您问题的更一般形式是：
给定一个未知长度的重复序列，请确定信号的周期。
确定重复频率的过程称为傅里叶变换。在您的示例情况下，信号是干净且离散的，但是以下解决方案即使在连续嘈杂的数据下也可以使用！该FFT将尝试通过在所谓的“波空间”或“傅立叶空间”接近他们复制的输入信号的频率。基本上，该空间中的峰值对应于重复信号。信号的周期与峰值的最长波长有关。
import itertools # of course this is a fake one just to offer an example def source(): return itertools.cycle((1, 0, 1, 4, 8, 2, 1, 3, 3, 2)) import pylab as plt import numpy as np import scipy as sp # Generate some test data, i.e. our "observations" of the signal N = 300 vals = source() X = np.array([vals.next() for _ in xrange(N)]) # Compute the FFT W = np.fft.fft(X) freq = np.fft.fftfreq(N,1) # Look for the longest signal that is "loud" threshold = 10**2 idx = np.where(abs(W)>threshold)[0][-1] max_f = abs(freq[idx]) print "Period estimate: ", 1/max_f
这可以为这种情况提供正确的答案，10尽管如果N不对周期进行清楚的划分，您将获得接近的估计。我们可以通过以下方式将其可视化：
10
N
plt.subplot(211) plt.scatter([max_f,], [np.abs(W[idx]),], s=100,color='r') plt.plot(freq[:N/2], abs(W[:N/2])) plt.xlabel(r"$f$") plt.subplot(212) plt.plot(1.0/freq[:N/2], abs(W[:N/2])) plt.scatter([1/max_f,], [np.abs(W[idx]),], s=100,color='r') plt.xlabel(r"$1/f$") plt.xlim(0,20) plt.show()
