4

それぞれの不完全な平方根の連分数の期間があるリストのリストを使用しています。

私がそれらを使ってやろうとしているのは、各リストで最大の繰り返しパターンのサイズをチェックすることです。

たとえば、いくつかのリスト：

[
 [1,1,1,1,1,1....],
 [4,1,4,1,4,1....],
 [1,2,10,1,2,10....],
 [1,1,1,1,1,4,1,4,1,20,9,8,1,1,1,1,1,4,1,4,1,20,9,8....],
 [2,2,2,4,2,2,2,4....],
 [1,1,1,13,21,45,3,3,1,16,4,1,4,1,1,1,24,15,1,1,1,13,21,45,3,3,1,16,4,1,4,1,1,1,24,15....],
 [1,1,1,3,28,1,1,1,3,28,67,25,1,1,1,3,28,1,1,1,3,28,67,25....]
]

私が取り組んできた2つの同様の方法は次のとおりです。

def lengths(seq):
    for i in range(len(seq),1,-1):
        if seq[0:i] == seq[i:i*2]:
            return i


def lengths(seq):
    for i in range(1,len(seq)-1):
        if seq[0:i] == seq[i:i*2]:
            return i

これらは両方ともリストのサイズを取得し、現在の位置からリストのインデックス付きサイズを比較します。問題は、最初の1桁が大きく始まり、1つの大きなパターンだけであるため、1桁の繰り返しに対して間違って返されることです。2番目の問題は、6番目と7番目の例のリストのようなネストされたパターンがあり、ネストされたループに満足し、パターンの残りの部分を見落とすことです。

4

5 に答える 5

4

作品（サンプルの4番目の要素でタイプミスを見つけました）

>>> seq_l = [
...  [1,1,1,1,1,1],
...  [4,1,4,1,4,1],
...  [1,2,10,1,2,10],
...  [1,1,1,1,1,4,1,4,1,20,9,8,1,1,1,1,1,4,1,4,1,20,9,8],
...  [2,2,2,4,2,2,2,4,2,2,2,4,2,2,2,4],
...  [1,1,1,13,21,45,3,3,1,16,4,1,4,1,1,1,24,15,1,1,1,13,21,45,3,3,1,16,4,1,4,1,1,1,24,15],
...  [1,1,1,3,28,1,1,1,3,28,67,25,1,1,1,3,28,1,1,1,3,28,67,25]
... ]
>>> 
>>> def rep_len(seq):
...     s_len = len(seq)
...     for i in range(1,s_len-1):
...         if s_len%i == 0:
...             j = s_len/i
...             if seq == j*seq[:i]:
...                 return i
...                 
... 
>>> [rep_len(seq) for seq in seq_l]
[1, 2, 3, 12, 4, 18, 12]
于 2012-07-09T22:54:24.943 に答える
2

リストを文字列に変換することが不可能でない場合は、正規表現を使用すると、これは簡単な作業になります。

import re

lists = [
    [1,1,1,1,1,1],
    [4,1,4,1,4,1],
    [1,2,10,1,2,10],
    [1,1,1,1,1,4,1,4,1,20,9,8,1,1,1,1,1,4,1,4,1,20,9,8], #I think you had a typo in this one...
    [2,2,2,4,2,2,2,4],
    [1,1,1,13,21,45,3,3,1,16,4,1,4,1,1,1,24,15,1,1,1,13,21,45,3,3,1,16,4,1,4,1,1,1,24,15],
    [1,1,1,3,28,1,1,1,3,28,67,25,1,1,1,3,28,1,1,1,3,28,67,25]
]

for l in lists:
    s = "x".join(str(i) for i in l)
    print s
    match = re.match(r"^(?P<foo>.*)x?(?P=foo)", s)
    if match:
        print match.group('foo')
    else:
        print "****"
    print

(?P<foo>.*)「foo」と呼ばれるグループを作成し、それに(?P=foo)一致させます。正規表現は貪欲であるため、デフォルトで最長の一致が得られます。「x？」中央の単一のxが偶数/奇数の長さを処理できるようにするだけです。

于 2012-07-09T23:00:41.053 に答える
1

気にしないサブリストがあることがわかっている場合を除いて、collections.defaultdict（int）を実行して、すべてのサブリストのカウントを保持することができます。サブリストを辞書キーにする前に、サブリストをタプルに変換します。

ただし、スペースが狭い場合は、一連のブルームフィルターを使用してどこかに到達できる可能性があります。長さ1のサブシーケンス用に1つのブルームフィルターがあり、長さ2のサブシーケンス用に別のブルームフィルターがあります。次に、衝突を取得する最大のブルームフィルターに最大長のサブリストがあります。

http://stromberg.dnsalias.org/~strombrg/drs-bloom-filter/

于 2012-07-09T22:13:58.483 に答える
0

一度に2つのレベルのシーケンスをチェックする必要があると思います。0..i == i..i*2および0..i/2 != i/2..i。 

def lengths(seq):
    for i in range(len(seq),1,-1):
        if seq[0:i] == seq[i:i*2] and seq[0:i/2] != seq[i/2:i]:
            return i

の2つの半分0..iが等しい場合は、実際に2つの連結されたパターンを互いに比較していることを意味します。

于 2012-07-09T22:35:01.063 に答える
0

最初のメソッド例から始めて、サブパターンを再帰的に検索できます。

def lengths(seq):
    for i in range(len(seq)-1,1,-1):
        if seq[0:i] == seq[i:i*2]:
            j = lengths(seq[0:i]) # Search pattern for sub pattern
            if j < i and i % j == 0: # Found a smaller pattern; further, a longer repeated
                # pattern length must be a multiple of the shorter pattern length
                n = i/j # Number of pattern repetitions (might change to // if using Py3K)
                for k in range(1, n): # Check that all the smaller patterns are the same
                    if seq[0:j] != seq[j*n:j*(n+1)]: # Stop when we find a mismatch
                        return i # Not a repetition of smaller pattern
                else: return j # All the sub-patterns are the same, return the smaller length
            else: return i # No smaller pattern

この解決策は完全には正しくないと感じますが、いくつかのテストを行い、必要に応じて編集します。（クイックノート：最初のforループはlen（seq）-1で開始するべきではありませんか？そうでない場合は、seq [0：len]をseq [len：len]と比較します。これはばかげているように見え、再帰がループする原因になります。無限に。）

編集：送信者が投稿した関連する質問のトップアンサーに似ているようですので、それを読んでください。;）

于 2012-07-09T22:41:13.630 に答える