7

無限のシーケンスで繰り返される数字を検出する方法は? Floyd & Brent検出アルゴリズムを試してみましたが、何も起こりませんでした... 0 から 9 (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長さのシーケンスがあります。LD_i = d_{i mod L}t_iitdD

定理

あなたが知っているシーケンスDが、いくつかの有限シーケンスによって生成されたとしますt。を生成するかどうかdを有限時間で決定することは不可能Dです。

証拠

限られた時間しか許可されていないため、 の有限数の要素にしかアクセスできませんD。の最初のF要素にアクセスするとしますD。最初の方法を選択したのはF、有限数へのアクセスしか許可されていない場合、アクセスした要素のインデックスを含むセットは有限であり、したがって最大値を持つためです。その最大値を としますM。これはF = M+1まだ有限数です。

とLの長さをdとD_i = d_{i mod L}しi < Fます。D_F同じかそうでないかの2 つの可能性がありd_{F mod L}ます。前者の場合dはうまくいくように見えますが、後者の場合はうまくいきません。にアクセスするまで、どちらの場合が真であるかはわかりませんD_F。ただし、これには要素へのアクセスが必要ですF+1が、要素へのアクセスに制限されていFます。

したがって、 が生成されるFかどうかを判断するのに十分な情報が得られないため、 が生成されるかどうかを有限時間で知ることは不可能です。dDdD

結論

dシーケンスがを生成しないことを有限時間で知ることは可能ですDが、これは役に立ちません。dを生成するシーケンスを見つけたいのでD、これにはとりわけ、いくつかのシーケンスが を生成することを証明できることが含まれDます。

Dこの問題に関する詳細情報がない限り、解決できません。dこの問題を決定可能にする 1 つの情報は、生成される最短の長さの上限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 ) の形式ではないため、Floyd や Brent のアルゴリズムは直接適用できません。ただし、タスクを実行するために拡張される場合があります。

  1. フロイドまたはブレントのアルゴリズムを使用して、シーケンスの繰り返し要素を見つけます。
  2. 同じ値を持つ次のシーケンス要素を見つけます。これらの要素間の距離は、想定される周期 ( k) です。
  3. kシーケンスの次の要素を記憶する
  4. この要素サブシーケンスの次のオカレンスを見つけますk。
  5. サブシーケンス間の距離が より大きい場合はk、更新kしてステップ 3 に進みます。
  6. 手順 4 を数回繰り返して、結果を確認します。反復サブシーケンスの最大長がアプリオリにわかっている場合は、適切な反復回数を使用します。それ以外の場合は、繰り返しごとに結果の正確さが増すため、できるだけ多くの繰り返しを使用してください。

シーケンスの循環が最初の要素から始まる場合、ステップ 1 を無視してステップ 2 から開始します (最初の要素に等しい次のシーケンス要素を見つけます)。

シーケンス サイクリングが最初の要素から始まらない場合、フロイドまたはブレントのアルゴリズムが、サイクルに属さないシーケンスの繰り返し要素を見つける可能性があります。したがって、ステップ 2 と 4 の反復回数を制限することは合理的であり、この制限を超えた場合は、ステップ 1 に進みます。

于 2012-06-26T11:10:31.913 に答える