7

如何检测无限序列中的重复数字？我尝试了Floyd & Brent检测算法，但一无所获……我有一个生成器，它产生的数字范围从 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)
4

4 回答 4

12

经验方法

这是一个有趣的问题。您的问题的更一般形式是：

给定一个未知长度的重复序列，确定信号的周期。

确定重复频率的过程称为傅立叶变换。在您的示例中，信号是干净且离散的，但即使使用连续的噪声数据，以下解决方案也适用！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()

在此处输入图像描述

于 2012-06-26T15:01:08.660 回答
4

Evgeny Kluev的答案提供了一种获得可能正确答案的方法。

定义

假设您有一些D重复序列。那就是有一些d长度序列L：D_i = d_{i mod L}，其中t_i是从 0 开始编号i的序列的第tdD

定理

给定一个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仅具有已知数量的有限状态，则可以计算此上限。

因此，我的结论是，除非您稍微更改规范，否则您无法解决此问题。

于 2012-06-26T14:43:04.093 回答
2

我不知道在此处应用适当的算法，但我的理解也是，如果您只使用了有限数量的术语，您永远无法确定您已经检测到一个周期。无论如何，这就是我想出的，这是一个非常幼稚的实现，更多的是从评论中教育而不是提供一个好的解决方案（我猜）。

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)

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

于 2012-06-26T15:37:48.593 回答
1

由于您的序列不是 X n+1 = f(X n ) 的形式，因此弗洛伊德或布伦特的算法并不直接适用于您的情况。但它们可能会被扩展来完成任务：

  1. 使用 Floyd 或 Brent 算法找到序列中的一些重复元素。
  2. 查找具有相同值的下一个序列元素。这些元素之间的距离是一个假定的周期 ( k)。
  3. 记住k序列的下一个元素
  4. 查找此k元素子序列的下一个匹配项。
  5. 如果子序列之间的距离大于k，则更新k并继续执行步骤 3。
  6. 重复步骤 4 几次以验证结果。如果重复子序列的最大长度是先验已知的，则使用适当的重复次数。否则使用尽可能多的重复，因为每次重复都会增加结果的正确性。

如果序列循环从第一个元素开始，则忽略第 1 步并从第 2 步开始（找到与第一个元素相等的下一个序列元素）。

如果序列循环不是从第一个元素开始的，那么 Floyd 或 Brent 的算法可能会找到不属于循环的序列的某些重复元素。所以限制步骤 2 和步骤 4 的迭代次数是合理的，如果超过这个限制，则继续步骤 1。

于 2012-06-26T11:10:31.913 回答