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....]
]

我一直在使用的两种类似方法是：

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

它们都采用列表的大小并从当前位置比较它的索引大小。问题是第一个仅针对一个重复数字返回错误，因为它开始很大并且看到的只是一个大模式。第二个的问题是存在嵌套模式，如第六个和第七个示例列表，它将满足嵌套循环并忽略模式的其余部分。

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 的子序列的布隆过滤器，另一个用于长度为 2 的子序列等。然后，发生冲突的最大布隆过滤器具有您的最大长度子列表。

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

于 2012-07-09T22:13:58.483 回答
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] 进行比较，这看起来很愚蠢，并且会导致递归循环无限地。）

编辑：似乎有点类似于发布的相关问题 senderle 中的最佳答案，所以你最好去读一下。;)

于 2012-07-09T22:41:13.630 回答
0

我认为你只需要一次检查两个级别的序列。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

如果 的两半0..i相等，则意味着您实际上是在比较两个连接的模式。

于 2012-07-09T22:35:01.063 回答