检测未知源的周期(Detect period of unknown source)

如何检测无限序列重复的数字？ 我尝试弗洛伊德和布伦特检测算法，但落空......我有一台发电机能产生数从0到9（含），我必须承认这一段。

实施例测试例：

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)

Answer 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没有分裂周期干净，你会得到一个接近的估计。 我们可以通过想象这样的：

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()

Answer 2:

叶夫根尼·Kluev的答案提供了一种方式来获得一个答案可能是正确的。

定义

让我们假设你有一些序列D是重复序列。 即有一些序列d长度的L使得： D_i = d_{i mod L}其中t_i是i个的序列元件t是从编号为0，我们将说序列d生成D 。

定理

给定一个序列D ，你知道，是一些有限序列产生的t 。 鉴于一些d是不可能在有限的时间内是否产生决定D 。

证明

由于我们只允许有限的时间，我们只能访问的元件的有限数目D 。 让我们假设我们进入第一F的元素D 。 我们选择的第一个F因为如果我们只允许访问有限数，包含我们访问的元素的索引的集合是有限的，因此具有最大的。 让那最大的是M 。 然后，我们可以让F = M+1 ，这仍然是一个有限数。

让L是的长度d ，并且D_i = d_{i mod L}为i < F 有两种可能性D_F它要么相同d_{F mod L}或不是。 在前一种情况下d似乎工作，但在后者的情况下，它没有。 我们无法知道，直到我们访问的情况下也是如此D_F 。 然而，这将需要访问F+1元素，但以我们被限制F元件存取。

因此，对于任何F我们将没有足够的信息来决定是否d产生D ，因此它是不可能在有限的时间是否知道d产生D 。

结论

有可能在有限的时间序列知道d 不产生D ，但这并不能帮助你。 既然你想找到一个序列d ，做产生D ，但是这涉及到除其他事项外能够证明一些序列生成D 。

除非你有更多的信息D这个问题是无法解决的。 一个比特的信息，这将使这个问题可判定是一些上界的最短的长度d ，生成D 。 如果知道函数生成D仅具有有限状态将已知量可以计算出这个上限。

因此，我的结论是，除非你修改规范一点，你解决不了这个问题。

Answer 3:

由于您的序列的形式X _{的n + 1} = F（X _n）的不，Floyd的或Brent的算法不直接适用于你的情况。 但是，他们可以延长到做任务：

1. 用弗洛伊德的或布伦特的算法找出序列的一些重复元素。
2. 查找具有相同的值下一个序列元素。 这些元件之间的距离是一个所谓的时间段（ k ）。
3. 记住下k的序列的元素
4. 找到这个下一个出现k -元素序列。
5. 如果子序列之间的距离是大于k ，更新k并继续执行步骤3。
6. 重复步骤4几次，以验证结果。 当该重复子序列的最大长度是已知的先验，使用重复的适当数量。 否则，使用尽可能多的重复越好，因为每次重复增加了结果的正确性。

如果序列循环从第一个元素开始，忽略步骤1和步骤2（找到等于第一元件下一个序列元素）启动。

如果序列循环不从第一个元素开始，有可能是弗洛伊德的或布伦特的算法认定，不属于周期序列的一些重复元素。 所以这是合理的限制步骤2和4的迭代次数，如果超过此限制，请继续步骤1。

Answer 4:

我不知道正确的算法思想在这里适用，但我的理解也是，你永远无法确切知道你已经发现如果你只消耗了条件有限数量的一个时期。 总之，这里是我想出的，这是一个非常幼稚的做法，更多地从教育的意见不是提供一个良好的解决方案（我猜）。

def guess_period(source, minlen=1, maxlen=100, trials=100):
    for n in range(minlen, maxlen+1):
        p = [j for i, j in zip(range(n), source)]
        if all([j for i, j in zip(range(n), source)] == p
               for k in range(trials)):
            return tuple(p)
    return None

这其中，然而，“忘记”的初始顺序，并返回一个元组是实际周期的循环置换：

In [101]: guess_period(gen)
Out[101]: (0, 1, 4, 8, 2, 1, 3, 3, 1, 1)

为了弥补这一点，你需要跟踪的偏移量。

文章来源: Detect period of unknown source